Offline RL via Feature-Occupancy Gradient Ascent

Venue: NeurIPS_cc_2024_Conference
Published: 2024-05-15 11:21:53

Abstract: We study offline Reinforcement Learning  in large infinite-horizon discounted Markov Decision Processes (MDPs) when the reward and transition models are linearly realizable under a known feature map. Starting from the classic linear-program formulation of the optimal control problem in MDPs, we develop a new algorithm that performs a form of gradient ascent in the space of feature occupancies, defined as the expected feature vectors that can potentially be generated by executing policies in the environment.	We show that the resulting simple algorithm satisfies strong computational and sample complexity guarantees, achieved under the least restrictive data coverage assumptions known in the literature. In particular, we show that the sample complexity of our method scales optimally with the desired accuracy level and depends on a weak notion of coverage that only requires the empirical feature covariance matrix to cover a single direction in the feature space (as opposed to covering a full subspace). Additionally, our method is easy to implement and requires no prior knowledge of the coverage ratio (or even an upper bound on it), which altogether make it the strongest known algorithm for this setting to date.

Main paper: 
 introduction: 
 We study Offline Reinforcement Learning (ORL) in sequential decision making problems whereby a learner aims to find a near-optimal policy with sole access to a static dataset of interactions with the underlying environment [Levine et al., 2020] . This line of work is naturally relevant to realworld tasks for which learning an accurate simulator of the environment is potentially intractable or impossible, trial-and-error learning could have grave consequences, yet logged interaction data is readily available. For example, in a high-stake application such as autonomous driving, building a sufficiently accurate simulator for the vehicle and its environment would require modelling very complex systems, which can be intractable both statistically and computationally. At the same time, running experiments in the real world could endanger the lives of other road users or result in damages to the vehicle. Yet, with the advent of tools for efficient sensory-data collection and processing, large volumes of logged data from human drivers are readily available.An efficient ORL method is one which finds a near-optimal policy after a tractable number of elementary computations and samples from the dataset. It is well-known in this setting that the quality of the solution has to heavily depend on the quality of the data, and in particular one cannot hope to find a near-optimal policy if the data covers the space of states and actions poorly. To formalize this intuition, many notions of data coverage have been proposed in the offline RL literature, ranging from a very restrictive uniform coverage assumption that requires the data-generating policy to cover the entire state-action space [Munos and Szepesvári, 2008] to a variety of partial coverage conditions whereby this exploratory condition is only required for state-action pairs that are of interest to the optimal policy [Liu et al., 2020 , Rashidinejad et al., 2021 , Uehara and Sun, 2021 , Zhan et al., 2022 , Rashidinejad et al., 2022 , Li et al., 2024] . In the present work, we study the setting of linear Markov Submitted to 38th Conference on Neural Information Processing Systems (NeurIPS 2024). Do not distribute.Decision Processes (MDPs) [Jin et al., 2020, Yang and Wang, 2019] where the reward and transition matrix admit a low rank structure in terms of a known feature map, and data-coverage assumptions can be defined in the space of features. As shown by [Zanette et al., 2021] , in this setting it is possible to obtain strong guarantees if the offline data is well-aligned with the expectation of the feature vector generated by the optimal policy (as opposed to requiring alignment with the entire distribution of features as required by other common offline RL methods [Jin et al., 2021 , Xie et al., 2021 , Uehara and Sun, 2021 , Zhang et al., 2022] ). In the present paper, we propose a simple and efficient algorithm that yields the best known sample complexity guarantees for this problem setting, all while only requiring the weakest known data-coverage assumptions of Zanette et al. [2021] .Our approach is based on the LP formulation of optimal control in infinite-horizon discounted MDPs due to Manne [1960] , and more specifically on its low-dimensional saddle-point reparametrization for linear MDPs proposed by Gabbianelli et al. [2024] (which itself builds on earlier work by Neu and Okolo, 2023 and Bas-Serrano et al., 2021) . Primal variables of this saddle-point objective correspond to expectations of feature vectors under the state-action distribution of each policy (called feature occupancies), and dual variables correspond to parameters of linear approximations of actionvalue functions. We design an algorithm based on the idea of optimizing the unconstrained primal function that is derived from the saddle-point objective by eliminating the dual variables via a classic dualization trick. More precisely, we design a sample-based estimator of the primal function and optimize it via a variant of gradient ascent in the space of feature occupancies.This approach is to be contrasted with the method of Gabbianelli et al. [2024] , which instead optimized the original saddle-point objective via stochastic primal-dual methods. Their algorithm interleaved a sequence of "policy improvement" steps with an inner loop performing "policy evaluation", which resulted in a suboptimal use of sample transitions due to the costly inner loop. This issue was addressed in the very recent work of Hong and Tewari [2024] who, instead of relying on stochastic optimization, built an estimator of the saddle-point objective and optimized it via a deterministic primal-dual method. Our approach is directly inspired by their idea of estimating the saddle-point objective, but our algorithm design is significantly simpler: instead of directly optimizing the primal function in terms of feature occupancies, Hong and Tewari [2024] relied on a sophisticated reparametrization of the primal variables, and used a computationally involved procedure to update the dual variables. Both of these steps required prior knowledge of a tight bound on the featurecoverage ratio of the optimal policy, which is typically not available in problems of practical interest. Such knowledge is not required by our algorithm, thanks to the incorporation of a recently proposed stabilization trick that we make use of in our algorithm [Jacobsen and Cutkosky, 2023, Neu and Okolo, 2024] . We provide a more detailed discussion of these closely related works in Section 5.Notation. We use boldface lowercase letters m to denote vectors and and bold uppercase M for matrices. We define the Euclidean ball in R Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?Answer: [Yes] Justification:Guidelines:• The answer NA means that the abstract and introduction do not include the claims made in the paper.• The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or NA answer to this question will not be perceived well by the reviewers.• The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.• It is fine to include aspirational goals as motivation as long as it is clear that these goals are not attained by the paper. 
preliminaries: 
 We consider infinite-horizon Discounted Markov Decision Processes (DMDPs) [Puterman, 1994] of the form (X , A, r, P , γ) where X denotes a finite (yet large) set of X states and A is a finite action space of cardinality A = |A|. We refer to r ∈ [0, 1] XA as the reward vector, P ∈ R XA×X + the transition matrix and γ ∈ (0, 1) the discount factor. For a state-action pair (x, a) ∈ X × A we also use the notation r (x, a) = r [(x, a) ] to denote the reward of taking action a in state x and p (x ′ |x, a) = P [(x, a) , x ′ ] as the probability of ending up in state x ′ afterwards.The MDP models a sequential decision making process where an agent interacts with its environment as follows. For each step k = 0, 1, 2, • • • ,, the agent observes the current state X k of the environment and then goes on to select its action A k . Based on this action in the current state, it receives a rewardr (X k , A k ), transits to a new state X k+1 ∼ p (•|X k , A k )and the process continues. The objective of the agent is to find a decision-making rule that maximizes its total discounted reward when the initial state X 0 is sampled according to a fixed initial-state distribution distribution ν 0 ∈ ∆ X . Without loss of generality, we assume that the initial state is fixed almost surely as X 0 = x 0 , and use ν 0 to refer to the corresponding delta distribution. It is known that this objective can be achieved by executing a stationary stochastic policy π : X → ∆ A , with π(a|x) denoting the probability of the agent selecting action A k = a in state X k = x for all k. We will use Π to denote the set of all such behavior rules and will often simply call them policies. We define the normalized discounted return of each policy π asρ (π) = (1 -γ) E ν0,π ∞ k=0 γ k r (x k , a k ) ,where the role of the discount factor γ ∈ (0, 1) is to emphasize the importance of earlier rewards, and the notation E ν0,π [•] highlights that the initial state is sampled from ν 0 and all actions are sampled according to the policy π. We will use π * to denote any policy that maximizes the return.We will consider the offline RL setting where we are given access to a data set of n sample transitionsD n = {(X i , A i , R i , X ′ i )} n i=1 , where X ′ i ∼ p(•|X i , A i ) is sampled independently for each i and R i = r(X i , A i ).Otherwise, no assumption is made about the state-action pairs (X i , A i ), and in particular we do not require these to be generated by a fixed behavior policy or to be independent of each other.For describing the approach we take towards solving this problem, we need to introduce some further standard notations. The value function and action-value function associated with policy π are respectively defined asv π (x) = E a∼π(•|x) [q π (x, a)] , q π (x, a) = E π ∞ k=0 γ k r (x k , a k ) x 0 = x, a 0 = a ,and the state-occupancy and state-action-occupancy measures under π asν π (x) = a µ π (x, a) , µ π (x, a) = (1 -γ) E ν0,π ∞ k=0 γ k I {x k ,a k } .The value functions and occupancy measures adhere to the following recursive equations, respectively termed the Bellman equation and Bellman flow condition [Bellman, 1966] :q π = r + γP v π , µ π = π • [(1 -γ) ν 0 + γP T µ π ].Here, the composition operation • is defined so that for any policy π and state distribution ν ∈ R X , we have(π • ν) (x, a) = π (a|x) ν (x). Notice that we can express the return of π in terms of value functions and occupancy measures as ρ (π) = (1 -γ) ⟨ν 0 , v π ⟩ = ⟨µ π , r⟩. On this note, for a given target accuracy ε > 0, we say policy π is ε-optimal if it satisfies µ π * -µ π , r ≤ ε.In the present work, we well make use of the linear MDP assumption due to Jin et al. [2020] , Yangand Wang [2019] , which is defined formally as follows:Definition 2.1 (Linear MDP). An MDP is called linear if both the transition and reward functions can be expressed as a linear function of a given feature map φ : X × A → R d . That is, there exist ψ : X → R d and ω ∈ R d such that, for every x, x ′ ∈ X and a ∈ A:r(x, a) = ⟨φ(x, a), ω⟩, p (x ′ |x, a) = ⟨φ(x, a), ψ(x ′ )⟩.We denote by Φ ∈ R |X ×A|×d the feature matrix with rows given by φ(x, a) T and Ψ ∈ R d×|X | as the weight matrix with columns ψ(x). Further, we will assume that∥ω∥ 2 ≤ √ d, that ∥Ψv∥ 2 ≤ B √ d holds for all v ∈ [-B, B],and that all feature vectors satisfy ∥φ(x, a)∥ 2 ≤ R for some R ≥ 1.An immediate consequence of this assumption is that the action-value function of any policy π can be written as a linear function of the features as q π = Φθ π , withθ π = ω + γΨv π ∈ R d .For the rest of the paper we explicitly assume that the feature matrix Φ is full rank -which is enough to ensure uniqueness of θ π . It is common to assume that the feature dimension d ≪ X such that the transition operator is low-rank. As common in this setting, we will suppose throughout the paper that the feature map Φ is known.Our algorithm design will be based on the linear programming formulation of MDPs, first proposed in a number of papers in the 1960's [Manne, 1960 , de Ghellinck, 1960 , d'Epenoux, 1963 , Denardo, 1970] . This formulation frames the problem of finding an optimal control policy as the following pair of primal and dual linear programs:EQUATIONminimize (1 -γ)⟨ν 0 , v⟩ subject to Ev ≥ r + γP v.(2)(E T µ) (x) = a∈A µ (x, a) , (Ev) (x, a) = v (x) .It is known that the occupancy measure of an optimal policy µ π * is an optimal solution of the primal LP (1). In fact, the feasible set of the primal is precisely the space of valid state-action occupancy measures that can be induced by stationary policies. Therefore, given any feasible solution µ, we can extract the inducing policy as π µ (a|x) = µ (x, a) / a ′ µ (x, a ′ ) when a µ (x, a) ̸ = 0. Likewise, the state value function of the optimal policy π * is an optimal solution to the dual LP. That said, since the LP features XA variables and constraints, it cannot be solved directly in large MDPs.In view of the above limitations, we consider the following reduced version of the above intractable LPs due to Gabbianelli et al. [2024] (see also Neu and Okolo, 2023, Bas-Serrano et al., 2021) :EQUATIONEQUATIONIn view of the second constraint of the primal LP (3), λ should be thought of as expectations of feature vectors under occupancy measures, and we thus refer to them as feature occupancy vectors. Similarly, the second constraint of the dual LP (4) suggests that θ should be thought of as parameters of the approximate action-value functionq θ = Φθ = Φ (ω + γΨv) = r+γP v. We use λ π * = Φ T µ π * todenote the feature occupancy associated with the optimal policy π * and θ π * to denote the parametervector of the optimal action-value function q π * . The Lagrangian corresponding to the LPs is given asEQUATIONIt is easy to verify that by the linear MDP property, the feasible sets of the above LPs coincide with those of the original LPs in an appropriate sense, and their optimal solutions correspond to the optimal state-action occupancy measure and state-value function respectively (see Appendix A).In order to further reduce the complexity of the LPs above, we introduce a policy π and parametrize the remaining high-dimensional variables v and µ asEQUATIONPlugging this choice back into the Lagrangian, we obtain the objectivef (λ, π; θ) = L(λ, µ λ,π ; v θ,π , θ) = (1 -γ)⟨ν 0 , v θ,π ⟩ + ⟨λ, ω + γΨv θ,π -θ⟩ (7) = ⟨λ, ω⟩ + ⟨θ, Φ T µ λ,π -λ⟩.It is easy to see that for any π and λ π = Φ T µ π , we have f (λ π , π; θ) = ⟨µ π , r⟩ for all θ ∈ R d . Furthermore, whenever λ ̸ = λ π then the θ-player has a winning strategy that can force min θ f (λ, π; θ) = -∞. This (informally) suggests that an optimal policy can be found by solving the unconstrained saddle-point optimization problem max λ∈R d ,π∈Π min θ∈R d f (λ, π; θ). Furthermore, since the optimal policy can be written as π * (a|x) = I {a=argmax b ⟨θ π * ,φ(x,b)⟩} , it is sufficient to consider softmax policies of the formΠ (D π ) = π θ (a|x) = e ⟨φ(x,a),θ⟩ a ′ e ⟨φ(x,a ′ ),θ⟩ θ ∈ B d (D π ) ,which can approximate π * to good precision when the diameter D π is set to be large enough. This parametrization effectively reduces the high-dimensional LP into a low-dimensional saddle-point optimization problem.3 Feature-occupancy gradient ascent for offline RL in linear MDPsA natural idea for developing RL methods is to build an empirical approximation of the function f defined in the previous section, and use primal-dual methods to find a saddle-point of the resulting approximation. For offline RL, this approach has been explored by Gabbianelli et al. [2024] and Hong and Tewari [2024] . In this work, we develop an alternative approach that seeks to directly optimize the return by approximately maximizing the unconstrained primal function f * : R d × Π, defined for each feature-occupancy vector λ and policy π asf * (λ, π) = min θ∈B d (D θ ) f (λ, π; θ),for an appropriately chosen feasible set B d (D θ ). Given the discussion in the previous section, maximizing this function with respect to λ and π is rightly expected to result in an optimal policy (which intuition will be made formal in our analysis). Notably, the so-called objective f in Equation ( 7)depends on the transition weight matrix Ψ which is unknown in general. As we soon show, this matrix dominates the loss of the θ-player and λ-player. Based on these observations, our approach consists of building a well-chosen estimator f of f , and then maximizing the associated primal function f * defined asf * (λ, π) = min θ∈B d (D θ ) f (λ; θ, π).The objective f is built via a least-squares estimator inspired by the classic LSTD model estimate of Bradtke and Barto [1996] , Parr et al. [2008] , which has been successfully used for analyzing finite-horizon linear MDPs in a variety of recent works (e.g., Jin et al., 2020, Neu and Pike-Burke, 2020) . In particular, we fit an estimator Ψ of the true matrix Ψ using samples from the datasetD n = {(X i , A i , R i , X ′ i )} n i=1 as follows. Let φ i = φ(X i , A i ) denote the feature vector of (X i , A i )andΛ n = βI n + 1 n n i=1 φ i φ Ti the empirical feature covariance matrix. We define the regularized least squares estimate of Ψ at x ∈ X asψ (x) = arg min ψ(x)∈R d 1 n n i=1 ⟨φ i , ψ (x)⟩ -I {x=X ′ i } 2 + β ∥ψ (x)∥ 2 2 ,so that the estimate can be written asEQUATIONWith this matrix at hand, we define f asf (λ, π; θ) = (1 -γ)⟨ν 0 , v θ,π ⟩ + ⟨λ, ω + γ Ψv θ,π -θ⟩ = ⟨λ, ω⟩ + ⟨θ, Φ T µ λ,π -λ⟩,where µ λ,π (x, a) = π(a|x) (1 -γ)ν 0 (x) + γ⟨ ψ(x), λ⟩ is a sample-based approximation of µ λ,π .For the purpose of optimization, we will employ appropriately chosen versions of mirror ascent [Nemirovski and Yudin, 1983, Beck and Teboulle, 2003] to iteratively optimize the primal variables. Denoting the iterates for each t = 1, 2, . . . , T by λ t and π t , and defining θ t = arg min θ∈B d (D θ ) f (λ t , π t ; θ), the updates are defined as follows. Using g λ (t) = ∇ λt f * (λ t , π t ) to denote the gradient of f * with respect to the feature occupancies, the first set of variables is updated asEQUATIONwhere the first regularization term acts as proximal regularization (necessary for mirror-ascent-style methods), and the second one has a stabilization effect whose role will be made clear later in the analysis. The resulting update can be written in closed form, and is equivalent to a preconditioned gradient-ascent step on f * . The policies are updated in each state-action pair x, a asπ t+1 (a|x) = π t (a|x)e α⟨φ(x,a),θt⟩ a ′ π t (a ′ |x)e α⟨φ(x,a ′ ),θt⟩ = π 1 (a|x)e α⟨φ(x,a), t k=1 θ k ⟩ a ′ π 1 (a ′ |x)e α⟨φ(x,a ′ ), t k=1 θ k ⟩ , Algorithm 1 Feature-Occupancy Gradient Ascent (FOGAS) Input: Learning rates α, ϱ, η, initial points λ 1 ∈ R d , π 1 ∈ Π (D π ) , θ0 = 0, and dataset D n . for t = 1 to T do // Value-parameter update Compute Φ T µ λt,πt = (1 -γ) a π t (a|x 0 )φ(x 0 , a) + γ 1 n n i=1 a π t (a|X ′ i )φ(X ′ i , a) φ i , Λ -1 n λ t θ t = arg min θ∈B d (D θ ) ⟨θ, Φ T µ λt,πt -λ t ⟩ // Policy update Update θt = θt-1 + θ t π t+1 = σ αΦ θt // Feature-occupancy update Compute Ψv θt,πt = 1 n Λ -1 n n i=1 φ i v θt,πt (X ′ i ) Compute g λ (t) = ω + γ Ψv θt,πt -θ t λ t+1 = 1 1+ϱη (λ t + ηΛ n g λ (t)) end for return π J with J ∼ U(1, • • • , T ).corresponding to performing an entropy-regularized mirror ascent step in each state x (cf. Neu et al., 2017) . We use the shorthand notation π t+1 = σ αΦ t k=1 θ k to denote the resulting softmax policy, and note that it is fully specified by a d-dimensional vector that can be stored compactly.After the final iterate is computed, the algorithm picks the index J uniformly at random and outputs the policy π J . We refer to the resulting algorithm as Feature-Occupancy Gradient AScent (FOGAS), and present its detailed pseudocode featuring the explicit expressions of λ t and θ t as Algorithm 1.The following theorem states our main result regarding the performance of FOGAS.Theorem 3.1. Let π 1 be the uniform policy and λ 1 = 0. Also setD θ = √ d/ (1 -γ), D π = αT D θand δ > 0. Suppose that we run FOGAS for T ≥ 2R 2 n log A log(1/δ) rounds with parameters β = R 2 /dT as well asα = 2 (1 -γ) 2 log A R 2 dT , ϱ = γ 320d 2 log (2T /δ) (1 -γ) 2 n , η = (1 -γ) 2 27R 2 d 2 T .Then, with probability at least 1 -δ, the following bound is satisfied for any comparator policy π * and the associated feature-occupancy vector λ π * = Φ T µ π * :E J µ π * -µ π J , r = O   λ π * 2 Λ -1 n + 1 1 -γ • d 2 log (2T /δ) n   ,with the expectation taken with respect to the random index J.The most important factor in the bound of Theorem 3.1 is ∥λ * ∥ 2 Λ -1n , which measures the extent to which the data D n covers the comparator policy π * in feature space. We accordingly refer to this quantity as the feature coverage ratio between the policy π * and the data set D n , and we discuss its relationship with other notions of data coverage in Section 5. Notably, the bound holds simultaneously for all comparator policies π * , and thus it can be restated in an oracle-inequality form.On the same note, FOGAS does not need any prior upper bounds on the comparator norm ∥λ* ∥ 2 Λ -1 n ,and in particular it does not project the iterates λ t to a bounded set. These nontrivial properties are enabled by a recently proposed stabilization trick due to Jacobsen and Cutkosky [2023] and Neu and Okolo [2024] , which amounts to augmenting the standard mirror-ascent update of Equation ( 9) with the regularization term ϱ 2 ∥λ∥ 2 Λ -1 n . Without this additional regularization, the bounds would feature an additional factor of the order 1T T t=1 ∥λ t ∥ 2 Λ -1n , which cannot be controlled without projecting the iterates and in any case make it impossible to prove a comparator-adaptive bound. We defer further discussion of the result to Section 5.Question: Does the paper discuss the limitations of the work performed by the authors?Answer: [Yes] Justification:Guidelines:• The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.• The authors are encouraged to create a separate "Limitations" section in their paper.• The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.• The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on a few datasets or with a few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.• The authors should reflect on the factors that influence the performance of the approach.For example, a facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting. Or a speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.• The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.• If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.• While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an important role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations. 
theory assumptions and proofs: 
 Question: For each theoretical result, does the paper provide the full set of assumptions and a complete (and correct) proof?Answer: [Yes]Answer: [NA] Justification: This is a theory paper, there is no data or code.Guidelines:• The answer NA means that paper does not include experiments requiring code.• Please see the NeurIPS code and data submission guidelines (https://nips.cc/ public/guides/CodeSubmissionPolicy) for more details.• While we encourage the release of code and data, we understand that this might not be possible, so "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for a new open-source benchmark).• The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https://nips.cc/public/guides/CodeSubmissionPolicy) for more details.• The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.• The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only a subset of experiments are reproducible, they should state which ones are omitted from the script and why.• At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).• Providing as much information as possible in supplemental material (appended to the paper) is recommended, but including URLs to data and code is permitted. 
analysis: 
 This section is dedicated to proving our main result, Theorem 3.1. While we have defined FOGAS as a "primal-only" algorithm above, its analysis will be most convenient if we regard it as a primal-dual algorithm with implicitly defined dual updates. In particular, we will view the updates of FOGAS as a sequence of steps in a zero sum game between two teams of players: the max players that control λ t and π t , and the min player that picks θ t . The min player uses the simple best-response strategy of picking θ t = arg min θ∈B d (D θ ) f (λ, π t ), and the other two players perform their updates via appropriate versions mirror ascent on their respective objectives. Importantly, the updates of the λ-player are based on the gradients of f * , which satisfyg λ (t) = ∇ λt f * (λ t , π t ) = ∇ λt min θ∈B d (D θ ) f (λ t , π t ; θ) = ∇ λt f (λ t , π t ; θ t ),where the last equality follows from an application of Danskin's theorem. This property enables a major conceptual simplification that allows the interpretation of the updates as optimizing the unconstrained primal f * directly. We refer the interested reader to Chapter 6 of Bertsekas [1997] for more context on such use of primal-dual analysis.More concretely, we make use of an analysis technique first developed by Neu and Okolo [2023] ,and further refined by Gabbianelli et al. [2024] and Hong and Tewari [2024] . The core idea is to introduce the dynamic duality gap defined on a sequence of iterates {(λ t , π t , θ t )} T t=1 produced by some iterative method, and a set of well-chosen comparators λ * , π * ; {θ * t } T t=1 asG T λ * , π * ; {θ * t } T t=1 = 1 T T t=1 (f (λ * , π * ; θ t ) -f (λ t , π t ; θ * t )) .Similar to Lemma 4.1 of Gabbianelli et al. [2024] , we show in Lemma 4.1 below that with an appropriate choice of the comparator points, we can relate the gap to the expected suboptimality of policy π J whereJ ∼ U(1, • • • , T ). We leave the proof in Appendix B.1.1. Lemma 4.1. Suppose that D θ = √ d/(1 -γ). Choose (λ * , π * , θ * t ) = Φ T µ π * , π * , θ πt ∈ R d × Π (D π ) × B d (D θ ) for t = 1, • • • , Twhere µ π * is a valid occupancy measure induced by π * .Then,E J µ π * -µ π J , r = G T Φ T µ π * , π * , {θ πt } T t=1 .We will show below that the dynamic duality gap can be written in terms of the regrets of each player and an additional term related to the estimation error of f , and then proceed to provide bounds on all of these quantities. Specifically, the regrets of each player with respect to each of their respective comparators are defined asR T (π * ) = T t=1 x ν * (x) a (π * (a|x) -π t (a|x)) q t (x, a), R T (λ * ) = T t=1 f (λ * , π t ; θ t ) -f (λ t , π t ; θ t ) = T t=1 ⟨λ * -λ t , ω + γ Ψv θt,πt -θ t ⟩, R T (θ * 1:T ) = T t=1 f (λ t , π t ; θ t ) -f (λ t , π t ; θ * t ) = T t=1 ⟨θ t -θ * t , Φ T µ λt,πt -λ t ⟩.where ν * = (1 -γ)ν 0 (x) + γ⟨ψ(x), λ * ⟩. Furthermore, we define the gap-estimation error asEQUATIONThe following lemma rewrites the duality gap using the above terms.Lemma 4.2. The dynamic duality gap satisfiesG T (λ * , π * , θ * 1:T ) = 1 T R T (π * ) + 1 T R T (λ * ) + 1 T R T (θ * 1:T ) + γ T err Ψ .The proof directly follows from a straightforward calculation similar to the proof of Lemma 4.2 of Gabbianelli et al. [2024] and Section E.1 of Hong and Tewari [2024] which is reproduced in Appendix B.1.2 for completeness. It remains to bound the regret of the players, as well as the gap-estimation error. An obstacle we need to face in the analysis is that our bound of the latter error term scale with 1T T t=1 ∥λ t ∥ 2 Λ -1n , which is undesirable given our aspiration to achieve bounds that scale only with the comparator norm ∥λ * ∥ 2 Λ -1 n without requiring prior upper bounds on this quantity (that would enable us to project the iterates to a bounded domain). This challenge is addressed by making use of the stabilization technique of Jacobsen and Cutkosky [2023] and Neu and Okolo [2024] in the updates for the λ-player, which effectively eliminates these problematic terms. We briefly outline the remaining parts of the analysis below.The regrets of each player are respectively controlled by the following three lemmas.Lemma 4.3. Suppose that ν * ∈ ∆ X . Let π 1 be the uniform policy which selects all actions with equal probability in each state. Under the conditions on the feature map in Definition 2.1, the regretof the π-player against π * satisfies 1 T R T (π * ) ≤ log A αT + αR 2 D 2 θ 2 .The proof is a standard application of the analysis of exponential-weight updates, stated as Lemma E.1.Lemma 4.4. Let λ 1 = 0 and C = 6β d + D 2 θ + 3d (1 + RD θ ) 2 + 3γ 2 dR 2 D 2 θ .Then, the regret of the λ-player against any comparator λ * ∈ R d satisfies1 T R T (λ * ) ≤ 1 2ηT + ϱ 2 ∥λ * ∥ 2 Λ -1 n + ηC 2 - ϱ 2T T t=1 ∥λ t ∥ 2 Λ -1 n .The proof (provided in Appendix B.2.2) follows from applying the standard analysis of composite- As we show in Appendix B.2.3, the above statement holds trivially thanks to the "best-response" definition of θ t . This concludes our regret analysis.The following statement (proved in Appendix B.3) provides a bound on err Ψ :Lemma 4.6. Suppose that ∥φ(x, a)∥ 2 ≤ R for all (x, a) ∈ X × A, D θ = √ d/(1 -γ) and α = 2 (1 -γ) 2 log A/R 2 dT to optimize R T (π * ).Then, for any T ≥ 2R 2 n log A log(1/δ) and and ξ ≥ 0, the following holds with probability at least 1 -δ:err Ψ ≤ 1 2ξ ∥λ * ∥ 2 Λ -1 n + 1 T T t=1 ∥λ t ∥ 2 Λ -1 n + T 2 ξ 320d 2 log (2T /δ) n (1 -γ) 2 .The proof follows from applying Lemmas 4.1 and Lemma 4.2 when(λ * , π * , θ * t ) = Φ T µ π * , π * , θ πt ∈ R d × Π (D π ) × B d (D θ ) for t = 1, • • • , T .Then, adding up the bounds stated in Lemmas 4.3-4.6 under the respective conditions, yieldsE J µ π * -µ π J , r ≤ d log (1/δ) n (1 -γ) 2 + 1 2ηT + ϱ 2 + γ 2ξT λ π * 2 Λ -1 n + ηC 2 + γ ξT -ϱ 1 2T T t=1 ∥λ t ∥ 2 Λ -1 n + γT ξ 320d 2 log (2T /δ) n (1 -γ) 2 .Then, setting ρ = γ ξT simplifies the second term and eliminates the third term. The claim then follows after optimizing the hyperparameters, with the full details provided in Appendix B.4.We discuss various aspects of our results below.Relation with previous work. As discussed in the introduction, our work draws heavily on previous contributions of Gabbianelli et al. [2024] and Hong and Tewari [2024] . In particular, our idea of building a least-squares estimator of the transition function is directly borrowed from the latter of these works, and our implicit update rule for θ t is also inspired by their work to a good extent. Their approach, however, failed to reach the same degree of efficiency due to a number of suboptimal design choices. First, they used an alternative parametrization of the feature occupancies which only allowed them to work under a more restrictive coverage condition, so that their bounds depend on ∥λ * ∥ Λ -2 n which can be much larger than the feature coverage ratio appearing in our bounds. Second, their algorithm required a prior upper bound on this coverage parameter, with the guarantees scaling with the bound rather than the actual coverage. Such bounds are typically difficult to obtain in practice.Third, the implementation of their algorithm required intricate computational steps necessitated by their feature-occupancy parametrization. Our work has successfully removed these limitations and reduced the complexity of their method, thanks to a new primal-only analysis style that we hope will find further uses in reinforcement learning.Computational and statistical efficiency. As can be inferred from our main result, the sample complexity of finding an ε-optimal policy using our algorithm is of the orderd 2 ∥λ * ∥ 2 Λ -1 n /ε 2 (1 -γ) 2 ,which is optimal in terms of scaling with ε. The rate can be improved to scale linearly with the feature coverage ratio ∥λ * ∥ Λ -1 n , if a tight upper bound is known on it which can be used for hyperparameter tuning. We find this scenario to be unlikely, and are curious to see if future work can attain this improved scaling without such prior knowledge. As for computational complexity, we point out that the cost of each iteration of our method scales linearly with the sample size n, due to having to compute the matrix-vector products Ψv θt,πt . Indeed, the matrix Ψ is sparse with n non-zero rows, and as such computing this product takes linear time in n. Since the iteration complexity of FOGAS scales linearly with the sample size n, this makes for an overall runtime complexity of order n 2 . This limitation is of course shared with all methods using the same least-squares transition estimator for the transition model, including all work that builds on Jin et al. [2020] , but we nevertheless wonder if a substantial improvement is possible on this front.Data coverage assumptions. The only works we are aware of that scale with the feature-coverage ratio ∥λ * ∥ Λ -1 n are due to Zanette et al. [2021] and Gabbianelli et al. [2024] . The latter work only achieves this bound under the assumption that the data is drawn i.i.d. from a fixed behavior policy with known feature covariance matrix, which is a much more restricted setting that we consider here. Such assumptions are not needed by Zanette et al. [2021] , however their results are restricted to the simpler finite-horizon MDP setting, and their algorithm is arguably more complex than ours.Using our notation, their approach can be interpreted as solving a "pessimistic" version of the the relaxed dual LP (4) that features some additional quadratic constraints. This approach is not computationally viable for the infinite-horizon discounted case we consider, as it requires solving a fixed-point equation with respect to the estimated transition operator (cf. Wei et al., 2021) .Possible extensions. Our approach can be extended and generalized in a variety of ways. First, following Gabbianelli et al. [2024] , we believe that it is straightforward to extend our analysis to undiscounted infinite-horizon MDPs. Second, we similarly believe that an extension to constrained MDPs is possible without major challenges, following Hong and Tewari [2024] . We did not pursue these extensions because we believe that they add little additional insight. There are other potential directions that we did not explore because we found them to be too ambitious for the moment.These include extending our results beyond linear MDPs to other MDP models with linear function approximation, including MDPs with low inherent Bellman rank (which may be within reach of the current theory, c.f. Zanette et al., 2020) , linearly Q π -realizable MDPs (which are known to be challenging, c.f. Weisz et al., 2022 Weisz et al., , 2024)) . Even more ambitiously, one can ask if it is possible to extend our methods to work under more general notions of function approximation. This looks very challenging given the central role of feature occupancies in our formalism, which are strictly tied to linear function approximation. We are nevertheless optimistic that the ideas presented in this work will find use in other contexts, possibly including nonlinear function approximation in the future.A.1 Properties of the relaxed LPIn this section we prove a basic result about the feasible sets of the relaxed linear programs defined in Equations ( 3) and (4). We remark that similar results have been previously shown in Proposition 4 of Bas-Serrano et al. [2021] and Appendix A.1 of Neu and Okolo [2023] .Lemma A.1. Suppose that the MDP satisfies the linear MDP assumption in the sense of Definition 2.1, consider the relaxed linear programs 3 and 4 and their respective feasible sets:M P Φ = (λ, µ) ∈ R d × R XA + E T µ = (1 -γ)ν 0 + γΨ T λ, λ = Φ T µ , M D Φ = (v, θ) ∈ R X × R d Ev ≥ Φθ, θ = ω + γΨv .Then, the following statements hold:• The set M = µ : (λ, µ) ∈ M P Φ coincides with the feasible set of the primal LP (1). Furthermore, for all (λ * , µ * ) ∈ arg max (λ,µ)∈M P Φ ⟨λ, ω⟩, we have that µ * is the occupancy measure of an optimal policy.• The set V = v : (v, θ) ∈ M D Φ coincides with the feasible set of the dual LP (2). Furthermore, the optimal value function v π * and the parameter vectorθ π * satisfying q π * = Φθ π * satisfy (v π * , θ π * ) ∈ arg min (v,θ)∈M D Φ (1 -γ) ⟨ν 0 , v⟩.Proof. We first show that for any feasible point µ of the LP (1), the tuple (λ, µ) is feasible for the relaxed LP with λ = Φ T µ. This choice of λ satisfies the second primal constraint by definition, so it remains to verify that the first constraint is also satisfied. Indeed, this follows fromE T µ -(1 -γ)ν 0 -γΨ T λ = E T µ -(1 -γ)ν 0 -γΨ T Φ T µ = E T µ -(1 -γ)ν 0 -γP T µ = 0,where we have used the linear MDP property to write Ψ T Φ T = P T in the first step and that µ is a valid occupancy measure in the last one. Conversely, supposing that (λ, µ) ∈ M P Φ are feasible for the relaxed LP, we have thatE T µ -(1 -γ)ν 0 -γP T µ = E T µ -(1 -γ)ν 0 -γΨ T Φ T µ = E T µ -(1 -γ)ν 0 -γΨ T λ = 0,thus verifying that µ is indeed a valid occupancy measure. Optimality of (λ * , µ * ) follows from the fact that for any (λ, µ) ∈ M P Φ , we can write the LP objective as ⟨λ, ω⟩ = ⟨µ, r⟩ by the linear MDP assumption, and the standard fact that any solution µ * to the primal LP 1 is the occupancy measure of an optimal policy (cf. Theorem 6.9.4 in Puterman, 1994) . This concludes the first part of the proof.For the second part of the proof, let us first consider a feasible solution v for the original dual LP (2).Then, the choice θ = ω + γΨv satisfies the second dual constraint by definition. The first constraint can be verified by writingEv -Φθ = Ev -r -γP v ≥ 0,where we used the choice of θ in the first step and the feasibility of v for the original LP in the second step. Conversely, supposing that (θ, v) ∈ M D Φ , we note thatEv -r -γP v = Ev -Φθ ≥ 0,which implies the feasibility of v in the LP 2. Optimality of v * for both LPs follows from the fact that their objectives are identical, and the standard fact that v * is an optimal solution of the dual LP (2) (cf. Theorem 6.2.2 in Puterman, 1994) .In this section, we provide performance guarantees for Algorithm 1 in terms of the expected suboptimality of the output policy π J , and in particular prove the lemmas provided in Section 4 in the main text. Auxiliary lemmas and technical results for proving some of these are included in Appendix E.We first prove our claims regarding the dynamic duality gap introduced in Section 4 of the main text. By definition of the the dynamic duality gap, we have thatG T Φ T µ π * , π * , {θ πt } T t=1 = 1 T T t=1 f (Φ T µ π * , π * ; θ t ) -f (λ t , π t ; θ πt ).Considering the first term, we see thatf (Φ T µ π * , π * ; θ t ) = Φ T µ π * , ω + θ t , Φ T µ λ * ,π * -Φ T µ π * (a) = µ π * , r + θ t , Φ T µ λ * ,π * -Φ T µ π * (b) = µ π * , r ,where we have used (a) the linear MDP property (definition 2.1) and (b) the following relation:µ λ * ,π * (x, a) = π * (a|x) (1 -γ)ν 0 (x) + γ ψ(x), Φ T µ π * = π * (a|x) (1 -γ)ν 0 (x) + γ x ′ ,a ′ p (x|x ′ , a ′ ) µ π * (x ′ , a ′ ) = µ π * (x, a).Now for the second term, we havef (λ t , π t ; θ πt ) = (1 -γ) ⟨ν 0 , v θ π t ,πt ⟩ + ⟨λ t , ω + γΨv θ π t ,πt -θ πt ⟩ = ⟨µ πt , r⟩ + ⟨λ t , ω + γΨv πt -θ πt ⟩ = ⟨µ πt , r⟩ ,where we have used the Bellman equations q πt = Φθ π t = r + γP v πt = Φ (ω + γΨv πt ), which together with the fact that Φ is full rank implies that θ πt = ω + γΨv πt . Substituting the above expressions for f (Φ T µ π * , π * ; θ t ) and f (λ t , π t ; θ πt ) in the dynamic duality gap and noting that πJ is such that 1 T T t=1 ⟨µ πt , r⟩ = E J [⟨µ π J , r⟩] we get G T Φ T µ π * , π * , {θ πt } T t=1 = E J µ π * -µ π J , r .This completes the proof.Recall that for any comparator points λ * , π * ; {θ * t } T t=1 , the dynamic duality gap is defined asG T λ * , π * ; {θ * t } T t=1 = 1 T T t=1 (f (λ * , π * ; θ t ) -f (λ t , π t ; θ * t )) .Then, by adding and subtracting some terms we express the dynamic duality gap in terms of the average loss of each player with respect to the objective f (λ, π; θ). This givesEQUATIONConsider the first set of terms from the above expression. By definition of f in Equation ( 7), we immediately obtain the instantaneous regret of the π-player asf (λ * , π * ; θ t ) -f (λ * , π t ; θ t ) = ⟨θ t , Φ T µ λ * ,π * -Φ T µ λ * ,πt ⟩ = x ν * (x) a (π * (a|x) -π t (a|x)) q t (x, a) = x ν * (x) a (π * (a|x) -π t (a|x)) q t (x, a),where ν * (x) = (1 -γ)ν 0 (x) + γ ⟨ψ(x), λ * ⟩.For the regret of the λ and θ-players, notice that we can express the estimator f in terms of the objective f as follows:f (λ, π; θ) = (1 -γ) ⟨ν 0 , v θ,π ⟩ + λ, ω + γ Ψv θ,π -θ = f (λ, π; θ) + γ λ, Ψv θ,π -Ψv θ,π .Taking advantage of this relation, we now consider the last two set of terms in Equation ( 11). Indeed, for the second set of terms in the equation, we writef (λ * , π t ; θ t ) -f (λ t , π t ; θ t ) = f (λ * , π t ; θ t ) -f (λ t , π t ; θ t ) -γ λ * , Ψv θt,πt -Ψv θt,πt + γ λ t , Ψv θt,πt -Ψv θt,πt = λ * -λ t , ω + γ Ψv θt,πt -θ t -γ λ * , Ψv θt,πt -Ψv θt,πt + γ λ t , Ψv θt,πt -Ψv θt,πt ,Notice that the last equality follows directly from definition of f . Along these lines, we can also express the last set of terms in Equation ( 11) as follows:f (λ t , π t ; θ t ) -f (λ t , π t ; θ * t ) = f (λ t , π t ; θ t ) -f (λ t , π t ; θ * t ) -γ λ t , Ψv θt,πt -Ψv θt,πt + γ λ t , Ψv θt,πt -Ψv θ * t ,πt = ⟨θ t -θ * t , Φ T µ λt,πt -λ t ⟩ -γ λ t , Ψv θt,πt -Ψv θt,πt + γ λ t , Ψv θt,πt -Ψv θ * t ,πt , Plugging the above derivations in the dynamic duality gap, we have thatG T (λ * , π * , θ * 1:T ) = 1 T T t=1 x ν * (x) a (π * (a|x) -π t (a|x)) q t (x, a) + 1 T T t=1 λ * -λ t , ω + γ Ψv θt,πt -θ t + 1 T T t=1 ⟨θ t -θ * t , Φ T µ λt,πt -λ t ⟩ + γ T T t=1 λ * , Ψv θt,πt -Ψv θt,πt + γ T T t=1 λ t , Ψv θ * t ,πt -Ψv θ * t ,πt .This matches the claim of the lemma, thus completing the proof.In this section we provide the proofs of the our claims made in the main text about the regret of each player-precisely, Lemmas 4.3-4.5.Consider the regret of the π-player introduced in the main text as,R T (π * ) = T t=1 x ν * (x) a (π * (a|x) -π t (a|x)) q t (x, a) (a) ≤ x ν * (x)D KL (π * (•|x)∥π 1 (•|x)) α + αT R 2 D 2 θ 2 (b) ≤ log A α + αT R 2 D 2 θ 2 .We have used (a) the standard Mirror descent analysis of softmax policy iterates recalled in Lemma E.1 for completeness, and (b) the fact that π 1 is a uniform policy and ν * ∈ ∆ X . Dividing the above expression by T completes the proof.Recall the total regret of the λ-player against any fixed comparator λ * ∈ R d is given asR T (λ * ) = T t=1 ⟨λ * -λ t , ω + γ Ψv θt,πt -θ t ⟩.Since the feature-occupancy updates of Algorithm 1 simply implements a version of the compositeobjective mirror descent scheme due to Duchi et al. [2010] we apply the standard analysis of this method (recalled as Lemma C.1 in Appendix C) to bound the instantaneous regret as⟨λ * -λ t , ω + γ Ψv θt,πt -θ t ⟩ ≤ ∥λ t -λ * ∥ 2 Λ -1 n -∥λ t+1 -λ * ∥ 2 Λ -1 n 2η + η 2 ∥Λ n g λ (t)∥ 2 Λ -1 n + ϱ 2 ∥λ * ∥ 2 Λ -1 n - ϱ 2 ∥λ t+1 ∥ 2 Λ -1 n .Then, taking the sum for t = 1, • • • , T , evaluating the telescoping sums and upper-bounding some negative terms by zero yields the expressionT t=1 ⟨λ * -λ t , ω + γ Ψv θt,πt -θ t ⟩ ≤ ∥λ 1 -λ * ∥ 2 Λ -1 n 2η + η 2 T t=1 ∥Λ n g λ (t)∥ 2 Λ -1 n + ϱT 2 ∥λ * ∥ 2 Λ -1 n - ϱ 2 T t=1 ∥λ t ∥ 2 Λ -1 n + ϱ 2 ∥λ 1 ∥ 2 Λ -1 n = 1 2η + ϱT 2 ∥λ * ∥ 2 Λ -1 n + η 2 T t=1 ∥Λ n g λ (t)∥ 2 Λ -1 n - ϱ 2 T t=1 ∥λ t ∥ 2 Λ -1 n .In the equality, we have used that λ 1 = 0. Dividing the resulting term by T gives the following bound on the average regret:1 T R T (λ * ) ≤ 1 2T η + ϱ 2 ∥λ * ∥ 2 Λ -1 n + η 2T T t=1 ∥Λ n g λ (t)∥ 2 Λ -1 n - ϱ 2T T t=1 ∥λ t ∥ 2 Λ -1 n .The proof is completed by applying Lemma C.2 to bound the norm of the gradients and plugging the result into the bound above.For the regret of the θ-player, first note that for any policy π with corresponding state-action value function weights θ π = ω + γΨv π , we have∥θ π ∥ 2 = ∥ω + γΨv π ∥ 2 ≤ ∥ω∥ 2 + γ ∥Ψv π ∥ 2 ≤ √ d + γ √ d (1 -γ) = √ d (1 -γ) ,where we have used the triangle inequality in the second line. The last inequality uses Definition 2.1 and the fact that ∥v π ∥ ∞ ≤ 1 (1-γ) since the rewards are bounded in [0, 1]. Thanks to this bound, we can ensure that θ * t = θ πt ∈ B d (D θ ) holds with the choice D θ = √ d/ (1 -γ) as required by the lemma.Therefore, by construction of value-parameter updates in Algorithm 1, we have⟨θ t -θ * t , Φ T µ λt,πt -λ t ⟩ ≤ 0 for t = 1, • • • , T.This concludes the proof.In this section, we provide the proof of Lemma 4.6 which bounds the gap-estimation error defined for an arbitrary comparator sequence(λ * , π t , θ * t ) ∈ R d × Π (D π ) × B d (D θ ) for t = 1, . . . , T as, err Ψ = T t=1 λ * , Ψ -Ψ v θt,πt + T t=1 λ t , Ψ -Ψ v θ * t ,πt .We control the above term with the now-classic techniques developed by Jin et al. [2020] for bounding model-estimation errors for linear MDPs. These results also make heavy use of self-normalized tail inequalities as popularized by Abbasi-Yadkori et al. [2011] (see also Lattimore and Szepesvári, 2020) .To make this clear, we first note that, for any λ ∈ R d , v ∈ R X , and ξ > 0,λ, Ψ -Ψ v (a) ≤ ∥λ∥ Λ -1 n Λ n Ψ -Ψ v Λ -1 n (b) ≤ ∥λ∥ 2 Λ -1 n 2T ξ + T ξ 2 Λ n Ψ -Ψ v 2 Λ -1 n .Here, we have first used (a) the Cauchy-Schwarz inequality, and (b) the inequality of arithmetic and geometric means. Using this expression, we can upper-bound the gap estimation error asEQUATIONEQUATIONTo control the last two terms in the bound, we employ two main lemmas stated below.Lemma B.1. Let v ∈ [-B, B] X. With probability at least 1 -δ, we have that:Λ n Ψ -Ψ v Λ -1 n ≤ 2B √ n d log 1 + R 2 dβ + 2 log 1 δ + B dβ. Lemma B.2. Consider the function class, V = v π,θ : X → [-RD θ , RD θ ] π ∈ Π (D π ) , θ ∈ B d (D θ ) ,Let D π = αT D θ so that v θt,πt ∈ V. For any ϵ ∈ (0, 1), with probability at least 1 -δ,Λ n Ψ -Ψ v θt,πt Λ -1 n ≤ 2RD θ √ n d log 1 + R 2 dβ + 4d log 1 + 4αT R 2 D 2 θ ϵ + 2 log 1 δ + RD θ dβ + β + 1 ϵ √ d.The rather tedious but otherwise standard proofs of the above lemmas are given in Appendix D. Now, taking into account the fact that for D θ large enough v πt ∈ V yields Corollary B.3 below.Corollary B.3. In the linear MDP setting described in Definition 2.1, notice that v πt = v θ π t ,πt withθ πt = ω + γΨv θ π t ,πt . Furthermore, with RD θ = R √ d/(1 -γ) ≥ ∥v πt ∥ ∞ and D π = αT D θ we have that v πt ∈ V.Therefore, for all ϵ > 0 with probability at least 1 -δ, the following holds:Λ n Ψ -Ψ v πt Λ -1 n ≤ 2 √ d √ n (1 -γ) d log 1 + R 2 dβ + 4d log 1 + 4αT R 2 d ϵ (1 -γ) 2 + 2 log 1 δ + d √ β (1 -γ) + β + 1 ϵ √ d.In the following, we apply these results to bound the last two terms in the right-hand side of Equation ( 12). Precisely, usingD θ = √ d/(1 -γ), α = 2 log A/R 2 D 2 θ T = 2 (1 -γ) 2 log A/R 2 dT(which follows from optimizing the regret of the π-player in Lemma 4.3), as well as ϵ =4αR 2 d/ (1 -γ) 2 = √ 32R 2 d log A (1-γ) √ Tand β = R 2 /dT we have that in any round t, with probability at least 1 -δ,Λ n Ψ -Ψ v θt,πt Λ -1 n ≤ 20d 2 log (2T /δ) n (1 -γ) 2 + R 2 d T (1 -γ) 2 + R 4 d log A T 2 + 32R 2 d 2 log A T (1 -γ) 2 .Likewise,Λ n Ψ -Ψ v πt Λ -1 n ≤ 20d 2 log (2T /δ) n (1 -γ) 2 + R 2 d T (1 -γ) 2 + R 4 d log A T 2 + 32R 2 d 2 log A T (1 -γ) 2 .Then plugging in the above bounds in Equation ( 12) with T ≥ 2R 2 n log A log(1/δ) , it follows that forD Ψ = 320d 2 log(2T /δ) n(1-γ) 2 , err Ψ ≤ ∥λ * ∥ 2 Λ -1 n 2ξ + T t=1 ∥λ t ∥ 2 Λ -1 n 2T ξ + T 2 ξD 2 Ψ ,with probability at least 1 -δ, thus proving the claim.To control the expected suboptimality of the output policy π J of Algorithm 1, we study the repective regret and gap-estimation error at the selected comparator points. Precisely, combining Lemma 4.1 and 4.2 whenEQUATION)where,R T (π * ) = T t=1 x ν * (x) a (π * (a|x) -π t (a|x)) q t (x, a), R T λ π * = T t=1 ⟨λ π * -λ t , ω + γ Ψv θt,πt -θ t ⟩, R T (θ * 1:T ) = T t=1 ⟨θ t -θ πt t , Φ T µ λt,πt -λ t ⟩ err Ψ = T t=1 λ π * , Ψ -Ψ v θt,πt + T t=1 λ t , Ψ -Ψ v πt .Notice that for this choice of λ * , by Definition 2.1 ν* (x) = (1 -γ)ν 0 (x) + γ⟨ψ(x), µ * ⟩ = ν π * (x)is a valid state occupancy measure. Next, introducing the bounds stated in Lemmas 4.3-4.6 under the required conditionsD θ = √ d/ (1 -γ), α = 2 (1 -γ) 2 log A/R 2 dT , D π = αT D θ = 2T log A/R 2 and T ≥ 2R 2 n log A log(1/δ) , as well as ξ ≥ 0 and D Ψ = 320d 2 log(2T /δ) n(1-γ) 2yields,E J µ π * -µ π J , r ≤ 2R 2 d log A (1 -γ) 2 T + 1 2ηT + ϱ 2 λ π * 2 Λ -1 n + ηC 2 - ϱ 2T T t=1 ∥λ t ∥ 2 Λ -1 n + γ 2T ξ λ π * 2 Λ -1 n + 1 T T t=1 ∥λ t ∥ 2 Λ -1 n + γT ξD 2 Ψ ,with probability at least 1-δ, whereC = 6β d + D 2 θ +3d (1 + RD θ ) 2 +3γ 2 dR 2 D 2 θ .Rearranging the bound and selecting ϱ = γ/ξT to eliminate the (potentially large) norm of the iterates, we obtainE J µ π * -µ π J , r ≤ d log (1/δ) n (1 -γ) 2 + 1 2ηT + ϱ 2 + γ 2ξT λ π * 2 Λ -1 n + ηC 2 + γ ξT -ϱ 1 2T T t=1 ∥λ t ∥ 2 Λ -1 n + γT ξD 2 Ψ = d log (1/δ) n (1 -γ) 2 + 1 2ηT + γ ξT λ π * 2 Λ -1 n + ηC 2 + γT ξD 2 Ψ .Furthermore, choosing ξ = 1/T D Ψ i.e ϱ = γD Ψ , we further simplify the above bound on the regret in terms of the optimization error arising from the policy and feature occupancy updates as,E J µ π * -µ π J , r ≤ d log (1/δ) n (1 -γ) 2 + 1 2ηT λ π * 2 Λ -1 n + ηC 2 + γ λ π * 2 Λ -1 n + 1 D Ψ .Moving our attention to our earlier bound on the norm of g λ (t),C = 6β d + D 2 θ + 3d (1 + RD θ ) 2 + 3γ 2 dR 2 D 2 θ ≤ 27R 2 d 2 (1 -γ) 2 .The inequality follows from our earlier choice of β = R 2 /dT and that T ≥ 1/d 2 . Plugging the values of C and D Ψ in the bound, then choosing η =(1-γ) 227R 2 d 2 T and using the conditionT ≥ 2R 2 n log A log(1/δ) ,we have that with probability at least 1 -δ,E J µ π * -µ π J , r ≤ d log (1/δ) n (1 -γ) 2 + λ π * 2 Λ -1 n + 1 27d 2 log (1/δ) 8n log A (1 -γ) 2 + γ λ π * 2 Λ -1 n + 1 320d 2 log (2T /δ) n (1 -γ) 2 = O   λ π * 2 Λ -1 n + 1 (1 -γ) d 2 log (2T /δ) n   .This completes the proof.Lemma C.1. (cf. Lemma 1 of Duchi et al. [2010] ) Let g λ (t) = ω + γ Ψv θt,πt -θ t Given λ 1 = 0 and ϱ, η > 0 and the sequence of iterates {λ t } T t=2 defined for t = 1, • • • , T as:EQUATION)Then, for anyλ * ∈ R d , ⟨λ * -λ t , ω + γ Ψv θt,πt -θ t ⟩ ≤ ∥λ t -λ * ∥ 2 Λ -1 n -∥λ t+1 -λ * ∥ 2 Λ -1 n 2η + η 2 ∥Λ n g λ (t)∥ 2 Λ -1 n + ϱ 2 ∥λ * ∥ 2 Λ -1 n - ϱ 2 ∥λ t+1 ∥ 2 Λ -1 n .Proof. The proof of Lemma C.1 follows directly from the referenced Lemma from Duchi et al.[2010]. Consider,⟨λ * -λ t , g λ (t)⟩ + ϱ 2 ∥λ t+1 ∥ 2 Λ -1 n - ϱ 2 ∥λ * ∥ 2 Λ -1 n = λ t+1 -λ * , -g λ (t) + 1 η Λ -1 n (λ t+1 -λ t ) + ϱΛ -1 n λ t+1 + ⟨λ t+1 -λ t , g λ (t)⟩ -λ t+1 -λ * , 1 η Λ -1 n (λ t+1 -λ t ) + ϱΛ -1 n λ t+1 + ϱ 2 ∥λ t+1 ∥ 2 Λ -1 n - ϱ 2 ∥λ * ∥ 2 Λ -1 n (a) ≤ ⟨λ t+1 -λ t , g λ (t)⟩ - 1 η λ t+1 -λ * , Λ -1 n (λ t+1 -λ t ) + ϱ λ * , Λ -1 n λ t+1 - ϱ 2 ∥λ t+1 ∥ 2 Λ -1 n - ϱ 2 ∥λ * ∥ 2 Λ -1 n (b) ≤ ⟨λ t+1 -λ t , g λ (t)⟩ + 1 η λ t+1 -λ * , Λ -1 n (λ t -λ t+1 ) (c) = ⟨λ t+1 -λ t , g λ (t)⟩ - 1 2η ∥λ t+1 -λ t ∥ 2 Λ -1 n + 1 2η ∥λ * -λ t ∥ 2 Λ -1 n -∥λ * -λ t+1 ∥ 2 Λ -1 n ≤ 1 η sup y∈R d y, ηΛ 1/2 n g λ (t) - 1 2 ∥y∥ 2 2 + 1 2η ∥λ * -λ t ∥ 2 Λ -1 n -∥λ * -λ t+1 ∥ 2 Λ -1 n (d) = η 2 ∥Λ n g λ (t)∥ 2 Λ -1 n + 1 2η ∥λ * -λ t ∥ 2 Λ -1 n -∥λ * -λ t+1 ∥ 2 Λ -1 n We have used (a)The first order optimality condition on Equation ( 14):For any λ ∈ R d , λ t+1 -λ, -g λ (t) + 1 η Λ -1 n (λ t+1 -λ t ) + ϱΛ -1 n λ t+1 ≤ 0.(b) The relation:ϱ λ * , Λ -1 n λ t+1 - ϱ 2 ∥λ t+1 ∥ 2 Λ -1 n - ϱ 2 ∥λ * ∥ 2 Λ -1 n = - ϱ 2 ∥λ t+1 -λ * ∥ 2 Λ -1 n ≤ 0. (c) By definition of the squared L 2 -norm for vectors a = Λ -1/2 n (λ t+1 -λ * ) and b = Λ -1/2 n (λ t -λ t+1 ): ⟨a, b⟩ = 1 2 -∥b∥ 2 2 + ∥a + b∥ 2 2 -∥a∥ 2 2 .Note that a and b are well defined since Λ n is both symmetric and positive definite.Rearranging the terms and plugging in g λ (t) = ω + γ Ψv θt,πt -θ t completes the proof.Finally, we will use the following result that bounds the gradient norms appearing in the bound above.Lemma C.2. Under the conditions of the linear MDP setting we have that,EQUATIONΛ -1 n ≤ 3 ∥β (ω -θ t )∥ 2 Λ -1 n + 3 1 n n i=1 φ i (r (x i , a i ) -⟨φ i , θ t ⟩) 2 Λ -1 n + 3γ 2 Λ n Ψv θt,πt 2 Λ -1 n .Now to bound each of the three terms, we use that∥β (ω -θ t )∥ 2 Λ -1 n ≤ 2β 2 Λ -1 n 2 d + D 2 θ ≤ 2β d + D 2 θ ,where the first inequality uses the assumption that ∥ω∥ 2 ≤ √ d (cf. Definition 2.1) andθ t ∈ B d (D θ ).Next, we have that1 n n i=1 φ i (r (x i , a i ) -⟨φ i , θ t ⟩) 2 Λ -1 n ≤ 1 n n i=1 ∥φ i ∥ 2 Λ -1 n |r (x i , a i ) -⟨φ i , θ t ⟩| 2 ≤ d (1 + RD θ ) 2 .The last step follows from the fact that the rewards are bounded in [0, 1],∥φ i ∥ ≤ R, θ t ∈ B d (D θ )and Equation ( 17). The last remaining term is bounded asEQUATIONΛ -1 n = 1 n n i=1 φ i v θt,πt (x ′ i ) 2 Λ -1 n ≤ 1 n n i=1 ∥φ i ∥ 2 Λ -1 n ∥v θt,πt ∥ 2 ∞ ≤ dR 2 D 2 θTherefore, we obtain∥Λ n g λ (t)∥ 2 Λ -1 n ≤ 6β d + D 2 θ + 3d (1 + RD θ ) 2 + 3γ 2 dR 2 D 2 θand this completes the proof.In this section, we prove the lemmas stated in Section B.3.By definition of Λ n Section 3 and Ψ in Equation ( 8), we can write:Λ n Ψ -Ψ v = Λ n 1 n Λ -1 n n i=1 φ i e T x ′ i v -βI n + 1 n n i=1 φ i φ T i Ψv = 1 n n i=1 φ i [v (x ′ i ) -⟨p (•|x i , a i ) , v⟩] -βΨvIn the last equality we used definition 2.1 to writeφ T i Ψ = p (•|x i , a i ) T . Let ξ i = v (x ′ i ) - ⟨p (•|x i , a i ) , v⟩. Then, Λ n Ψ -Ψ v Λ -1 n ≤ 1 n n i=1 φ i ξ i Λ -1 n + ∥βΨv∥ Λ -1 n .We easily control the second term with the relation:EQUATIONThe last inequality follows from the fact thatΛ -1/2 n 2 ≤ 1/ √ β and by definition 2.1 ∥Ψv∥ 2 ≤ B √ d for v ∈ [-B, B] X .Now, to handle the first term, let D 0 = ∅. We construct a filtrationF i-1 = D i-1 ∪ (x 0 i , x i , a i , r i ) for i = 1, 2, • • • , n.Notice that by construction of the dataset ξ i is a martingale difference sequence(i.e E [ξ i |F i-1 ] = 0) taking values in the range [-2B, 2B]. Then, we can directly apply Lemma E.3to obtain a bound on the first term as:1 n n i=1 φ i ξ i Λ -1 n = 1 √ n n i=1 φ i ξ i 2 (nΛn) -1 ≤ 2B √ n 2 log det (nΛ n ) 1/2 det (nβI) -1/2 δ ≤ 2B √ n d log 1 + R 2 dβ + 2 log 1 δ .with probability 1 -δ. In the last inequality we have used the AM-GM inequality and bound on the feature vectors:det (nΛ n ) ≤ tr (nΛ n ) d d = nβ + tr ( n i=1 φ i φ T i ) d d ≤ nβ + nR 2 d d .Putting everything together, we have that w.p 1 -δ,Λ n Ψ -Ψ v Λ -1 n ≤ 2B √ n d log 1 + R 2 dβ + 2 log 1 δ + B dβ.This completes the proof.Unlike Lemma B.1, we now aim to control the error termΛ n Ψ -Ψ v Λ -1 n when v is random.Also, notice that with π 1 (a|x) = e ⟨φ(x,a),0⟩a ′ ∈A e ⟨φ(x,a ′ ),0⟩ as the uniform policy, for t = 1, • • • , T we have that,π t+1 (a|x) = π 1 (a|x)e α⟨φ(x,a), t k=1 θ k ⟩ a ′ π 1 (a ′ |x)e α⟨φ(x,a ′ ), t k=1 θ k ⟩ = e ⟨φ(x,a),α t k=0 θ k ⟩ a ′ e ⟨φ(x,a ′ ),α t k=0 θ k ⟩ , where θ 0 = 0. Furthermore, since {θ t } T t=1 ⊂ B d (D θ ), for any t α t k=0 θ k 2 ≤ αT D θ . Hence, with D π = αT D θ , π t ∈ Π (D π ) and v θt,πt ∈ V.Therefore, as we have seen in previous works [Jin et al., 2020, Hong and Tewari, 2024] , the quantityΛ n Ψ -Ψ v θt,πt Λ -1n can be controlled without any dependence on the size of the state space with a uniform covering argument over V. Let C v be an ϵ-cover of V. That is, for v πt,θt ∈ V, thereexists v ′ ∈ C v such that ∥v π,θt -v ′ ∥ ∞ ≤ ϵ.Then, we can write:EQUATION)Consider the first term in the bound. Note that v ′ is still random with respect to uncertainty in the learning process. However, due to the structure of V we know that C v exists and has cardinalitylog |C v | = O d log 1 + 4RDπRD θ ϵ (see Lemma E.6).Inspired by Lemma B.1, consider the event:E v = exists v ∈ C v : Λ n Ψ -Ψ v Λ -1 n > 2RD θ √ n d log 1 + R 2 dβ + 2 log 1 δ ′ +RD θ dβSince C v ⊆ V, we know from Lemma B.1 that P (E v ) ≤ δ ′ . Now, taking the union bound over the cover C v we have that,P v∈Cv E v ≤ |C v |δ ′ .Therefore for any v ′ ∈ C v with probability at least 1 -δ,Λ n Ψ -Ψ v ′ Λ -1 n ≤ 2RD θ √ n d log 1 + R 2 dβ + 2 log |C v | δ + RD θ dβ ≤ 2RD θ √ n d log 1 + R 2 dβ + 4d log 1 + 4RD π RD θ ϵ + 2 log 1 δ + RD θ dβNow, for the second term in Equation ( 16) we write,Λ n Ψ (v θt,πt -v ′ ) 2 Λ -1 n = 1 n n i=1 φ i (v θt,πt (x ′ i ) -v ′ (x ′ i )) 2 Λ -1 n (a) ≤ 1 n n i=1 |v θt,πt (x ′ i ) -v ′ (x ′ i )| 2 ∥φ i ∥ 2 Λ -1 n ≤ ϵ 2 1 n n i=1 ∥φ i ∥ 2 Λ -1 n (b) ≤ ϵ 2 d.We have used (a) Jensen's inequality and (b) since Λ n ≻ 0, the relation,EQUATIONFor the last term, notice that:∥Λ n Ψ (v ′ -v θt,πt )∥ Λ -1 n = βΨ (v ′ -v θt,πt ) + 1 n n i=1 φ i x ′ p (x ′ |x i , a i ) (v ′ (x ′ ) -v θt,πt (x ′ )) Λ -1 n (a) ≤ ϵ dβ + 1 n n i=1 φ i x ′ p (x ′ |x i , a i ) (v ′ (x ′ ) -v θt,πt (x ′ )) 2 Λ -1 n (b) ≤ ϵ dβ + 1 n n i=1 ∥v ′ -v θt,πt ∥ 2 ∞ ∥φ i ∥ 2 Λ -1 n (c) ≤ ϵ dβ + ϵ √ d = ϵ √ d β + 1 .This follows from (a) Equation ( 15)since v = v ′ -v θt,πt ∈ [-ϵ, ϵ]X and (b) monotonicity of the square root function as well as Jensen's inequality and (c) Equation ( 17).Finally, plugging the above results back into Equation ( 16), we have that with probability at least1 -δ, Λ n Ψ -Ψ v θt,πt Λ -1 n ≤ 2RD θ √ n d log 1 + R 2 dβ + 4d log 1 + 4RD π RD θ ϵ + 2 log 1 δ + RD θ dβ + β + 1 ϵ √ dThe proof of Lemma B.2 is complete.Lemma E.1. Let q 1 , • • • , q t be a sequence of iterates satisfying ∥q t ∥ ∞ ≤ RD θ by virtue of definition 2.1 and θ t ∈ B d (D θ ). Given an initial policy π 1 and learning rate α > 0, and sequence of policies {π t } T t=2 defined as: ,a) a ′ π t (a ′ |x)e αqt(x,a ′ ) , Then, for any comparator policy π * and ν * some state distribution,π t+1 (a|x) = π t (a|x)e αqt(xT t=1 x ν * (x) a (π * (a|x) -π t (a|x)) q t (x, a) ≤ x ν * (x)D KL (π * (•|x)∥π 1 (•|x)) α + αT R 2 D 2 θ 2 .The proof of the lemma follows from bounding the regret of the π-player in each state x asT t=1 a (π * (a|x) -π t (a|x)) q t (x, a) ≤ D KL (π * (•|x)∥π 1 (•|x)) α + α 2 T t=1 ∥q t (x, •)∥ 2 ∞ ,via the application of the standard analysis of the exponentially weighted forecaster of Vovk [1990] , Littlestone and Warmuth [1994] , Freund and Schapire [1997] (see, e.g., Theorem 2.2 in Cesa-Bianchi and Lugosi, 2006) , and noting that ∥q t ∥ ∞ ≤ RD θ for all t.Lemma E.2. Suppose that ∥φ(x, a)∥ 2 ≤ R for all (x, a) ∈ X × A. Let π θ , π θ ′ be softmax policies.Then, for all states x ∈ X we have that:a |π θ (a|x) -π θ ′ (a|x)| ≤ R ∥θ -θ ′ ∥ 2 holds for any θ, θ ′ ∈ R d .Proof. Recall that, Π (D π ) = π θ (a|x) = e ⟨φ(x,a),θ⟩ a ′ e ⟨φ(x,a ′ ),θ⟩ θ ∈ B d (D π ) .For π θ , π θ ′ ∈ Π (D π ) using Pinsker's inequality we have that,EQUATIONFurthermore, taking into account the specific structure of the policies, we can write: et al. [2011] ) Let {F i-1 } ∞ i=1 be a filtration and {ξ i } ∞ i=1 a real-valued stochastic process such that ξ iD KL (π θ (•|x)∥π θ ′ (•|x)) = a π θ (a|x) log π θ (a|x) π θ ′ (a|x) = - a π θ (a|x) ⟨φ(x,for i = 1, • • • is zero-mean (i.e E [ξ i |F i-1 ] = 0) and conditionally s-subgaussian for s ≥ 0. That is, for all b ∈ R, E e bξi |F i-1 ≤ e b 2 s 2 2 . Also, let {φ i } ∞ i=1 be F i-1 -measurable. Then, n i=1 φ i ξ i 2 (nΛn) -1 ≤ 2s 2 log det (nΛ n ) 1/2 det (nβI) -1/2 δ .Lemma E.4. (e.g. see Chapter 27 of Shalev-Shwartz and Ben-David [2014] ) For all ϵ > 0,log N (B d (r), ∥•∥ ∞ , ϵ) ≤ d log 1 + 2r ϵ .Corollary E.5. Under the conditions of Lemma E.2, for all ϵ > 0,log N Π (D π ) , ∥•∥ ∞,1 , ϵ ≤ log N B d (D π ), ∥•∥ ∞ , ϵ R ≤ d log 1 + 2RD π ϵ .Lemma E.6. Consider the function class,V = v π,θ : X → [-RD θ , RD θ ] π ∈ Π (D π ) , θ ∈ B d (D θ ) ,we have that:N (V, ∥•∥ ∞ , ϵ) ≤ N Π (D π ) , ∥•∥ ∞,1 , ϵ/2RD θ × N (B d (D θ ), ∥•∥ 2 , ϵ/2R) ,and, log N (V, ∥•∥ ∞ , ϵ) ≤ 2d log 1 + 4RD π RD θ ϵ Proof. Let C π+ a∈A π ′ (a|x) ⟨φ(x, a), θ -θ ′ ⟩ ≤ RD θ a∈A |π(a|x) -π ′ (a|x)| + R a∈A π ′ (a|x) ∥θ -θ ′ ∥ 2 Let C v = v π,θ : X → [-RD θ , RD θ ] π ∈ C π , θ ∈ C θ . Then, C v is an ϵ-cover of V with respectto the L ∞ -norm when ϵ π = ϵ/2RD θ and ϵ θ = ϵ/2R. Therefore, we can derive a bound on the covering number of C v as:N (V, ∥•∥ ∞ , ϵ) ≤ N Π (D π ) , ∥•∥ ∞,1 , ϵ/2RD θ × N (B d (D θ ), ∥•∥ 2 , ϵ/2R) ≤ 1 + 4RD π RD θ ϵ d 1 + 4RD θ ϵ d . Hence, log N (V, ∥•∥ ∞ , ϵ) ≤ 2d log 1 + 4RD π RD θ ϵThis completes the proof.NeurIPS Paper Checklist 
experimental setting/details: 
 Question: Does the paper specify all the training and test details (e.g., data splits, hyperparameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?Answer: [NA] Justification: This is a theory paper, there are no experiments.Guidelines:• The answer NA means that the paper does not include experiments.• The experimental setting should be presented in the core of the paper to a level of detail that is necessary to appreciate the results and make sense of them.• The full details can be provided either with the code, in appendix, or as supplemental material. 
experiment statistical significance: 
 Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?Answer: [NA] Justification: This is a theory paper, there are no experiments.Guidelines:• The answer NA means that the paper does not include experiments.• The authors should answer "Yes" if the results are accompanied by error bars, confidence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper.• The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).• The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)• The assumptions made should be given (e.g., Normally distributed errors).• It should be clear whether the error bar is the standard deviation or the standard error of the mean.• It is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have a 96% CI, if the hypothesis of Normality of errors is not verified.• For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out of range (e.g. negative error rates).• If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text. 
experiments compute resources: 
 Question: For each experiment, does the paper provide sufficient information on the computer resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?Answer: [NA] Justification: This is a theory paper, there are no experiments.Guidelines:• The answer NA means that the paper does not include experiments.• The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.• The paper should provide the amount of compute required for each of the individual experimental runs as well as estimate the total compute.• The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make it into the paper). 
code of ethics: 
 Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics https://neurips.cc/public/EthicsGuidelines?Answer: [Yes] Justification:Guidelines:• The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.• If the authors answer No, they should explain the special circumstances that require a deviation from the Code of Ethics.• The authors should make sure to preserve anonymity (e.g., if there is a special consideration due to laws or regulations in their jurisdiction). 
broader impacts: 
 Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?Answer: [NA] Justification: This is a theory paper, with no specific societal impacts foreseen in the near future.Guidelines:• The answer NA means that there is no societal impact of the work performed.• If the authors answer NA or No, they should explain why their work has no societal impact or why the paper does not address societal impact.• Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.• The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is a direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.• The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.• If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML). 
safeguards: 
 Question: Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?Answer: [NA] Justification: This is a theory paper, this question is not relevant.Guidelines:• The answer NA means that the paper poses no such risks.• Released models that have a high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.• Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.• We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make a best faith effort.12. Licenses for existing assets Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?Answer: [NA] Justification: This is a theory paper, there are no assets used.Guidelines:• The answer NA means that the paper does not use existing assets.• The authors should cite the original paper that produced the code package or dataset.• The authors should state which version of the asset is used and, if possible, include a URL.• The name of the license (e.g., CC-BY 4.0) should be included for each asset.• For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided.• If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswithcode.com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of a dataset.• For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.• If this information is not available online, the authors are encouraged to reach out to the asset's creators. 
new assets: 
 Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?Answer: [NA] Justification: This is a theory paper, there are no new assets.Guidelines:• The answer NA means that the paper does not release new assets.• Researchers should communicate the details of the dataset/code/model as part of their submissions via structured templates. This includes details about training, license, limitations, etc.• The paper should discuss whether and how consent was obtained from people whose asset is used.• At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file. 
crowdsourcing and research with human subjects: 
 Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well as details about compensation (if any)?Answer: [NA] Justification: This is a theory paper, we haven't used crowdsourced data or worked with human subjects.Guidelines:• The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.• Including this information in the supplemental material is fine, but if the main contribution of the paper involves human subjects, then as much detail as possible should be included in the main paper.• Justification: This is a theory paper, we haven't worked with human subjects.Guidelines:• The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.• Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.• We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurIPS Code of Ethics and the guidelines for their institution.• For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.2 for y ∈ R d . 
 
 Appendix:  


Decision: This paper studied offline Reinforcement Learning in large infinite-horizon discounted MDPs with linear realizability. It is based on a linear program formulation, and gradient descent in the feature occupancy space. The new algorithm enjoys favorable compuational and sample complexity guarantees, under weak data coverage assumptions. The algorithm and analysis appeared to be new to me, though the LP framework for offline RL has been well-studied in the recent literature of offline RL. There were some concerns regarding the similarity and technical novelty compared with a few literature, especially Zanette (2021) and Hong and Tewari (2024). In fact, the series of previous works by Gabbianelli et al. (2024) and Hong and Tewari (2024) diminished the novelty of the present paper. Moreover, as claimed to be a simple and "easy-to-implement" algorithm, no experimental results were implemented/compared. I agree that as a theory-oriented paper, experiments are not always necessary, but since this is an "algorithm" paper, with focus on the simplicity and implementability of the algorithm, it would have been stronger to really demonstrate this through experiments. It is a borderline paper, and I would recommend the authors incorporate the comments from this round to improve the paper, and consider resubmitting to upcoming ML venues.

Reviews: review: paper_summary: paper_summary: This paper provides an approach for solving Offline RL problems in domains where the underlying MDP problem has reward and transition models that are linearly realisable under a known feature map. The paper is well presented.
strength_weakness: strength_weakness: 1. This work is only for MDPs where rewards and transitions are linear. Many of the moderately interesting problems are not linearly realisable, so it is quite important that authors provided a detailed discussion on how it can be addressed. 
2. I am not entirely confident about this, so will wait for inputs from authors. The approach seems to be built based on works by Hong and Tiwari, and stabilisation trick [Neu and okolo, Jacobson et al.]. I was not sure on the key significant contributions of this paper on top of those works. 
3. For me the biggest concern is that there are no experimental results. How would such an approach work for an MDP where the transition and reward models are not linear? Also, the approach is still approximate (given the bound), so would have been important to show the real results.
questions: questions: Apart from the questions mentioned above in weaknesses, can the authors also provide answers to the following questions:
1. Theorem 3.1 is mentioned as the most important results. However, I am not clear on why it is a significant result? Why is this bound good?
2. Also the feature coverage ratio provided by this algorithm, why is it significant? And do others also achieve this ratio for Linear MDPs only or in the more general case?
limitations: limitations: There is no limitations mentioned.
paper_summary: paper_summary: This paper propose a new algorithm for offline reinforcement learning in linear infinite-horizon discounted MDP, which achieves a strong sample complexity under the weakest data coverage assumption. Moreover, their algorithm is easy to implement and computationally efficient. Their algorithm design is based on a reduced version of linear programming formulation of MDP, which approximately transforms the original problem into a unconstrained saddle-point optimization problem.
strength_weakness: strength_weakness: The paper is pretty notation heavy and a bit hard to follow. I would suggest including a table of notations with descriptions. The choices of notation can also be optimized. For example, I found the mixed use of $D_{\pi}$ and $D_{\theta}$ confusing, and they looks like they are dependent on the value of $\pi$ and $\theta$.
questions: questions: 1. is there a way to output a single policy (not a uniformly sampled policy) that achieves the same sample complexity?
2. I am wondering whether your algorithm can be extended to the stochastic shortest path setting [1, 2], which include finite-horizon MDP and discounted infinite-horizon MDP as special cases.

[1] Yin, M., Chen, W., Wang, M., and Wang, Y.-X. Offline stochastic shortest path: Learning, evaluation and towards optimality
[2] Chen, L., Jain, R., and Luo, H. Improved no-regret algorithms for stochastic shortest path with linear mdp
limitations: limitations: Nothing necessary stands out.
paper_summary: paper_summary: This paper studies the offline policy optimization problem, i.e. to find a policy whose value function is close to the optimal value function using offline samples.  Under the assumption of linear MDP, they proposed a gradient ascent algorithm. 

The sample complexity of the algorithm only depends on the feature coverage of the best policy and does not require coverage over any other policies.
strength_weakness: strength_weakness: Compared to Zanette (2021), the algorithm idea is somehow similar. Specifically, both algorithms use the actor-critic update, and the optimization in the algorithm of this paper is similar to the pessimism estimation in Zanette (2021).

The assumption made in this paper is the linear MDP assumption, which is stronger than the assumption in Zanette (2021).
questions: questions: Can your results extend to the case under linear Q-function and linear Bellman completeness assumptions?
limitations: limitations: Yes. The authors addressed all the limitations listed in the guidelines.

Comments: comment: Thank you very much for your response. I do not have further questions.