Offline Actor-Critic for Average Reward MDPs
Authors: William Powell
Jeongyeol Kwon
Qiaomin Xie
Hanbaek Lyu
Venue: NeurIPS 2025 poster ()
Keywords: Reinforcement Learning
Offline
Actor-Critic
Primary area: reinforcement_learning

Abstract: We study offline policy optimization for infinite-horizon average-reward Markov decision processes (MDPs) with large or infinite state spaces. Specifically, we propose a pessimistic actor-critic algorithm that uses a computationally efficient linear function class for value function estimation. At the core of our method is a critic that computes a pessimistic estimate of the average reward under the current policy, as well as the corresponding policy gradient, by solving a fixed-point Bellman equation, rather than solving a successive sequence of regression problems as in finite horizon settings. This procedure reduces to solving a second-order cone program, which is computationally tractable. Our theoretical analysis is based on a weak partial data coverage assumption, which requires only that the offline data aligns well with the expected feature vector of a comparator policy. Under this condition, we show that our algorithm achieves the optimal sample complexity of  O(\varepsilon^{-2})  for learning a near-optimal policy, up to model misspecification errors.

Offline Actor-Critic for Average Reward MDPs
William Powell Department Mathematics University of Wisconsin-Madison
Jeongyeol Kwon Wisconsin Institute for Discovery Madison, WI 53706 j jeongyeol kwon@wisc edu
Madison, WI 53706 igpowelleiisc.eo edu
Qiaomin Xie
Hanbaek Lyu Department of Mathematics University of Wisconsin-Madison
Department Industrial and Systems Engineering University of Wisconsin-Madison
Madison, WI 53706 wwlammin..iewwisccce..
Madison, WI 53706 hlyu@math. wwsc. edu
Abstract
We study offline policy optimization for infinite-horizon average-reward Markov decision processes (MDPs) with large or infinite state spaces. Specifically, we propose a pessimistic version of actor-critic methods using a computationally efficient lincar function class for value function estimation. At the core of our method a critic that computes a pessimistic estimate of the average reward under the current policy, well as the corresponding policy gradient, by solving fixed- point Bellman equation, rather than solving a successive sequence of regression problems in finite horizon settings. Due to the nature of volicy-based method, the critic only needs to solve a linear optimization problem with convex quadratic constraints. We show that a very mild data coverage requirement is sufficient for our algorithm to achieve (ss-²) sample complexity for learning near-optimal policy up model misspecification errors. To our knowledge, this is the first result with optimal dependence in the offline average reward setting.
Introduction
Reinforcement learning (RL) a sequential decision making framework commonly studied in the online setting where an agent attempts to learn an optimal policy through active interactions with its environment. However, in many relevant applications such as autonomous driving and health care, online learning can be intractable or dangerous [Tang and Wiens, 2021]. In such cases, it is common resort to offtine learning, where the agent's 's goal is learn a near-optimal policy from a static data set which was collected in a manner known to be safe and efficient for the application.
Without the ability to actively explore the environment, the agent's capability learn is subject to the quality of the collected data. In particular,
well known that effective learning is difficult impossible if the data set does not sufficiently
the space of states and actions. Thus, major challenge in offline RL is the design of algorithms with provable guarantees under the weakest possible data coverage requirements. Initial work [Antos al., 2007, Munos and Szepesvári, 2008] rely on strong uniform coverage assumptions that effectively require the data generating policy to visit the entire state-action space. However, this assumption is often unreasonable, especially for large or infinite state spaces. Accordingly, more recent work [Rashidinejad et al., 2021, Zanette et al., 2021, Zhan al., 2022, Hong and Tewari, 2024, Li et al., 2024, Gabbianelli al., 2024, Neu and Okolo, 2025] have focused on provable guarantees depending only partial coverage conditions
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

where the data set is only required to cover the subset of state-action pairs visited by an optimal policy.
State spaces in contemporary applications of RI. can be very large or even infinite. Such applications necessitate the use of some form of function approximation for computational and memory efficient representation of policies and value functions. Empirical results show the promise of both simple linear models as well as more complex forms of function approximation such as neural networks, but there are still important theoretical gaps to be filled. This is especially true for infinite horizon MDPs, where value functions are solutions to a fixed point Bellman equation. As such, classical backward induction techniques that work well for episodic MDPs do not apply.
Our particular interest in this paper is offline RL for infinite horizon average reward MDPs (AMDPs) with linear function approximation. AMDPs are appropriate for continuing tasks such as inventory management [Giannoccaro and Pontrandolfo, 2002] admission control [Weber et al., 2024], where there is no forced reset as in the episodic setting, or discounting that may lead to a myopic focus on short-term rewards. It is commonly acknowledged that theoretical analysis of algorithms for AMDPs is more challenging than that in the episodic or discounted setting. There are two primary reasons. First, as mentioned earlier, the techniques for episodic cases are not applicable here. Second, unlike discounted MDPs, the Bellman operator for AMDPs is not a contraction. Consequently, methods for discounted MDPs that rely on this contraction property do not carry over to the average reward setting.
In recent years, there have been a number of works investigating algorithms for AMDPs in the online setting [Fruit et al., 2018, Wei et al., 2020, 2021, Hao et al., 2021, Zhang and Xie, 2023, Agrawal and Agrawal, 2025, Hong al., 2025], and learning from generative model [Jin and Sidford, 2020, 2021, Zurek and Chen, 2024], as well as from deep RL and optimization perspectives [Zhang and Ross, 2021, Suttle et al., 2023, Agnihotri al., 2024, Bai et al., 2024]. However, our understanding of the offline setting remains limited, especially with function approximation. The only work we know is Primal-Dual Offiin RL (PDOR) [Gabbianelli et al., 2024], which only achieves sub-optimal O( 4) sample complexity guarantee. Furthermore, PDOR's 's theoretical results require the strong assumption that the MDP's rewards and transition obey an exact linear structure, which rarely holds in practice. Motivated by this gap in the literature, the main question we ask in this work is the following:
Can we design provably efficient algorithm for offline reinforcement learning in average reward MDPs with function approximation under minimal assumptions?
We make strides towards an affirmative answer to this question by designing a pessimistic actor-critic algorithm using linear function approximation with a known feature map. Our key observation is that under our policy-base based approach. pessimistic estimate of the Bellman operator's fixed point can be computed by solving simple linear optimization problem with convex quadratic constraints. We show our algorithm achieves optimal convergence rate guarantees with dependence on a measurement of data coverage used in prior work [Zanette et al., 2021, Gabbianelli et al., 2024, Neu and Okolo, 2025], which is referred to as the feature coverage rutio. This quantity a measurement of how well the dataset aligns with the expected feature vector when following an optimal policy x². Our result's ' dependence on the intrinsic quantitics improves over on the best known result for both average reward and discounted MDPs [Neu and Okolo, 2025]. Importantly, we do not require the MDP itself to obey any linear structure; our results hold under the more general conditions of approximate realizability and Bellman closedness. Furthermore, we only require the transition dynamics to satisfy a mild requirement that is significantly weaker than the uniform ergodicity assumption commonly considered for AMDPs [Wei et al., 2020, 2021, Bai et al., 2024]. Under these conditions, we show that Ō( samples are sufficient to learn a policy which is c-optimal up to a model misspecification error.
1.1 Additional Related Work
Aside from the previously mentioned work [Zanette et al., 2021], another paper [Jin et al., 2021] also studies offline RL with linear function approximation in episodic MDPs. Their algorithm is a form of pessimistic least-squares value iteration, where pessimism is enforced through an additive bonus as commonly adopted in the online setting. It not clear, however, whether this form of value iteration can be generalized to infinite horizon MDPs for the reasons discussed in the introduction.

---

Another line of related work studies offline RL in discounted MDPs with partial coverage and general function approximation [Xie et al., 2021, Cheng et al., 2022]. They also consider approximate realizabiliity and Bellman closedness conditions similar to ours. The information theoretic results by [Xie et al., 2021] are near optimal, but due to their generality, theoretically optimal implementation of these algorithms is intractable. A computationally efficient alternative is presented in [Xie et al., 2021], IJ but with sub-optimal convergence guarantees even when specialized to the linear setting. Similarly, convergence rates from the work [Cheng et al., 2022] are only of order N N-1/3 for N data samples.
Finally, most closely related this work the papers by [Zanette al., 2021, Gabbianelli et al., 2024, Hong and Tewari, 2024, Neu and Okolo, 2025]. We provide a detailed comparison with these works in Section 5.
2
Notation
For any set X, we let ( be the set of all probability distributions on X. Given a state space S, action space A, transition kernel P A A(S), and (stationary) policy : S A(A), the notation E [-] is the expectation with respect to Markov chain with transition kernel P* (ss,s') En т (a|s) Ps''ss, a) conditioned on starting in state E S. For a function RS we also use f as short hand for the conditional expectation and probability measure μ E ASS), & π is the probability measure on S x A defined by (μ & (s, a) = ((s)tT(als). Finally, given a symmetric, positive definite matrix A E Rdxd ||x]|a denotes the norm on Ed defined by vx Ax.
the notation f
(f) For policy
Preliminaries
3.1 Average Reward MDPs
Let S be large possibly infinite state space and A be finite space of A actions. We consider
an infinite horizon average reward MDP (S, A. with transition kernel P: : S x A- + A A and reward function S x A + [0. 1]. An agent's rule for decision making in the MDP is specified by a (stationary) policy π + (AA) that maps current states to distributions over actions. At each time step the agent observes state s,, takes action a, T T--(s,), receives reward r(st, at). then transitions to state 84+1 ~ P(. (s, at). The agents goal is to find a policy maximizing the average
reward, which is defined as follows:
(*)(s = lim
E
Σ 1=
r(s at)
(1)
T
For each policy n, define its associated Bellman operator T -RSXA RSXA
T (" a) = r(s, a) + Bxyx-Pttaaaasssxxreeelllll a)), VsES,aEA.
We will consider the following assumption throughout the paper.
Assumption 3.1. All (stationary) policies induce a Markov chain that contains single recurrent class and possibly some transient states (unichain). This implies that (' is a constant independent of the initial state. Furthermore, it implies that for each policy π there exists a function q" S x + R. unique up to linear translations, satisfying the Bellman equation
T"" ="=
VsES,
(2)
which we will call the q-function. In this case, (s) EaNa(ia))a (s, is called the value function. We also assume there exists a constant e. such that
suplla" 11 Se
where 11p" sups,e (s, inf a (s, a) is the span somi-
3

---

Under Assumption 3.1, for each policy there exists unique stationary measure jr" satisfying the equation
Σx Σ [(als) = (s'),,
and we can write
J (
As will be seen in the sequel, it is crucial for our algorithm that JR is constant and Assumption 3.1 is sufficient to guarantee this. This assumption also allows us to reliably estimate a bounded q-function (2), which is necessary for stability in the policy improvement step of our algorithm.
We note that Assumption 3.1 stronger than the weakly communicating assumption often considered in the online learning literature [Jaksch al., 2010, Fruit al., 2018, Wei et al., 2021, Hong et al., 2025]. However, is important to point out one crucial fact. This assumption does not imply exploratory conditions such uniformly lower bounded stationary measures [Wei al., 2020] or uniformly excited features condition [Hao et al., 2021, Wei et al., 2021]. These exploratory conditions imply that cover the states visited by any policy, it necessary to cover the entire state space. For more details on this, we refer the reader to Appendix A where we provide more thorough discussion on the implications of Assumption 3.1 and comparison with other average reward models from the literature.
3.2
Offline RL
In offline RL., the agent only has access to a pre-collected data D {(Si, ag Pi, N where = r(8;, a;) and each s sampled from the conditional distribution P(-|s,, a;) independently of everything else. We do not need any additional assumptions about the collection of the data in D. As in [Zanette et al., 2021, Neu and Okolo, 2025], the data does not need to be generated from i.i.d. sampling for from following fixed behavior policy.
3.3 Function Approximation
Function approximation is necessary for learning in MDPs with large state and action spaces, where tabular solution methods are intractable. For actor-critic methods, this typically means using one function class to represent policies, and another class F for value function estimation. Effective learning in the MDP then becomes highly dependent the ability accurately represent the true value functions for a given policy и E II using functions in F. To quantify this ability, we introduce the following definition.
Definition 3.2. Let F. C. RSSA be set of functions used for value function approximation and (N : A(A)} class of stationary policies.
(i) We say that (F, II) satisfies the approximate realizability property with constant KF, if
sup 9E
inf
||g + -- T gl S KF..-
(i)) The tuple (F,II) said satisfy the Bellman--rstricted closedness property with constant F if
sup inf lgg 1T SFF.T FEII,EF.INNI1
These definitions are average-reward-aae -naloouuss of those for episodic MDPs |Zanette al., 2021, Nguyen- Tang and Arora, 2023]. Similar notions appeared in discounted MDPs in Xie et al. [Xie al., 2021], although our use of the lox norm slightly stronger than their requirement.
The approximate realizability property states that F nearly contains qºt for each policy æ E II. K5,n then the infimum in (3) is attained by (g, A) J").
However, realizability alone known to be insufficient for sample efficient learning [Wang et al., 2021]. Therefore, additional conditions are often required. Restricted closedness measures how well

---

we can perform regression using functions 9 E F when the target is the function resulting from the application of T a function f E JF plus a reasonable estimate À of J The addition of À here is generalization inspired, in part, by the requirement for linear MDPs that the column span of the feature matrix contains the all-one vector [Wei et al., 2021, Gabbianelli et al., 2024), as well as the development of generalized advantage estimation for the average reward setting in [Zhang and Ross, 2021] which includes a monte-carlo estimate J as part of the regression target.
With these definitions, we can now introduce the function and policy classes considered for our algorithm.
Assumption 3.3. We consider the use of linear function class
Q(Bw) = {g(s, a) ((5, (0(s,a) a) T w || 2 S Bw)
where Bw is a user-defined parameter and Φ S x A - R$ is known d-dimensional feature map with lØ(s, a)ll S 1. We also assume a softmax policy class
(l(o,a)
(Taas))
0 R
(4)
We assume that (Q(Bw), II) satisfies the approximate completeness and Bellman-restricted closed- ness properties with constants (Q(B.),11 and (,) respectively.
This assumption is generalization of the widely studied linear MDP model, which is first introduced for episodic MDPs [Jin et al., 2020] and adapted to the average reward setting [Wei et al., 2021, Hong al., 2025, Gabbianelli et al., 2024] with the realizability and restricted closedness constants being zero. Note that if the value functions are unbounded, it is unreasonable to assume approximate realizability. One cannot expect the ability approximate functions in unbounded set up to uniform error with an bounded function class. This is why we need the bounded span requirement in Assumption 3.1. However, we do not require prior knowledge of the constant i Assumption 3.1 for our results. Our theoretical guarantees remain true for any choice of Bw provided Assumptions 3.1 and 3.3 hold.
4 Algorithm Details
Our algorithm is a form of pessimistic actor-critic method for the average reward setting. At a high level, it works through an alternating scheme run for total number of K iterations. First, at iteration k, given the pessimistic critic first computes the smallest plausible average reward of my within a confidence region determined by the dataset D. Then the actor updates the policy T through conservative policy improvement step.
4.1 Pessimistic Policy Evaluation
Before giving more precise description, we start with motivating discussion of natural idea inspired by methods in the episodic setting, but which turns out not to work in our setting. Assume for moment that have completed iterations of the algorithm, and we have estimate JR of the average reward n and an estimate 0ş of the value function for policy тę. Then by the Bellman equation (2), it is natural estimate the q-function Th by solving the ridge regression problem
N
wt E arg min wERd
as)
T w + Jr - -r; 0n(x))) + 1m
which has the closed form expression
Wk
A
* a:) (r-- ox(s)))
(5)
Here, Å is the un-normalized empirical covariance matrix
N
((, a, (o(s),)sss. 0:) +I,
5

---

and I is the d-dimensional identity matrix. Let 9 (s) o(s, a) we be our estimate of q==. This method is similar to the typical approach for episodic MDPs, where the value function of step h + 1 is estimated and then used as regression target to compute the weight vector for step h.
There are main issues with this approach, however, in AMDP setting. The first issue is about estimating JTh in AMDPs, which we will address shortly. The second issue, also shared with discounted MDPs, is that the Bellman equation in our case is a fixed point equation. Consequently, we cannot use backward induction techniques from episodic MDPs. Therefore, it is unclear how to construct the estimated value 0g if haven't 't already obtained an estimated Q-function á without resorting to Monte-Carle methods. However, as pointed out in prior work [Zanette et al., 2021] I Monte- Carlo estimation undesirable in the offline setting: using importance sampling weights to cancel the distribution mismatch requires some knowledge of the data generating distribution, which not available in most offline settings.
One method to address the second problem is to use -x-1, i.e. a value function estimate from the previous iteration, as the regression target (e.g. as in the work [Moulin and Neu, 2023]). However, this incurs additional bias and results in an additional term in the sub-optimality guarantee that must be handled in the analysis. This is usually done by showing that the difference in value functions between consecutive policies is small due to the conservative policy update. However, it remains unclear how address this issue for AMDPs without strengthening Assumption 3.1 include, for example, uniform mixing assumption.
We propose to bypass these additional complexities and directly solve for the fixed point equation. Since wP parametrizes our q-function estimates, we should also have (x)s) (-Is) (o(s, TTTTk)/Tw "w]] Therefore, we replace du (s() in (5) with o= (s]) wx, where 6= Eawae (-1s) (0{s, a)]. Inspired by the ideas of Zanette et al. [2021], J. we then add a perturbation & E IR to the weight vector and solve the following optimization problem:
(urk, Jk) E arg min
J
w w.EEK"JER
s.t. w - Σ Mss ai) (r(si, az) - a:)
(6))
(6)
J 11 ||ll|2 S Bw, and |KEl S
where is parameter determined by Bw, K, N, (Q(Ba),T (Q(B)). and a confidence level 5 E (0, 1). Specifically,
B=C+ (NQ(B.)) ( EQUB,))
where
C= C=OOBe//llg(AABBB/b))
(8)
This parameter quantifies the uncertainty in the dataset and our knowledge of the true MDP. The addition of & is how pessimism is incorporated into the algorithm. The ellipsoid ||E|| < 3 can be viewed as confidence set which, with high probability, contains the error due to lack of knowledge of the true transition. In our analysis, we will show that Js is nearly pessimistic estimate of T up to misspecification error determined by the constant x x.......II This approach also similar to the FOPO algorithm [Wei et al., 2021] for the online setting, but with one crucial difference: because our algorithm is policy-based policy rather than the Bellman optimality equation. Consequently, the feasible set in (6) is convex, being comprised of linear and convex quadratic constraints. Therefore, approximate solutions to this optimization problem, up to arbitrarily small error, can be computed in polynomial time with interior point methods [Nesterov and Nemirovskii, 1994]. This stands in stark contrast to the FOPO algorithm, where our linear constraint in (6) is replaced by the analogous but nonlinear constraint
the first constraint in (6) is based on the Bellman equation for a fixed
N
w = = + A-1
Σ
((8,, az) (r(ss, as) - max( (ww)) w))
The nonlinearity comes from the additional maximization operation. This results in non-convex constraint set and an optimization problem to be solved at every iteration without a known efficient computation method,

---

Finally, we remark here that while fully efficient implementation of our algorithm would involve only approximate solutions (6), for simplicity will assume that (wg, & .&k is an exact solution for the remainder of the paper. We refer the interested reader to Section B of the appendix where we briefly discuss error propagation for a fully efficient implementation of our algorithm where (6) solved approximately at each step.
4.2
Policy Update
Once the weight vector wy is computed, the policy parameter is updated via
0 x+1 < 0x + m/wk
where 77 log A BER K
is step-size. Due to the form of policy class (4), this is equivalent to the
exponential weights update
[k]s(a x (als) exp (17 a)), where (s(s,,) a) o(s a ww
which, in turn, equivalent to one step of mirror ascent with KI. divergence regularization. Once the algorithm is terminated, it returns the output policy Tout which is mixture policy defined the uniform random sampling of policies { k The pscudo code of our algorithm is presented in Algorithm 1.
Algorithm Average Reward Actor-Critic
1: Input: D (dataset), Bnd (function class parameter), 3 (uncertainty parameter), 7) (stepsize)
2: Form empirical covariance Å + I+ EN (88, (;)) as)
3: Initialize: 01 =
4: for k == 1..... K do
5: Let (wx, Ex. Jv) solve (6)
6: Update policy parameter: O2+1 &- Os + 1/00k.
7: end for
8: Output: Tout = Unif(m1....... Tk]
5 Main Results
Let ÅN = A be the normalized covariance matrix. For a given comparator policy ा with stationary measure μt, let d" = &(s..))=r& [Ø(s, a)] E Idd. The sub-optimality of the mixture policy Tout output by Algorithm with respect comparator policy depends on the random constant
| NAw"
referred to as the feature coverage ratio in [Gabbianelli et al., 2024, Neu and Okolo, 2025]. It measures how well the dataset D covers the feature space visited by æ. When the expected feature vector d'd is aligned with the top eigenvector of the empirical covariance matrix Å, one should expect this constant to be small-this is the case when D consists primarily of state-action pairs who's feature vectors are closely aligned with those frequently visited when following policy æ. Our converge ratio can be contrasted with that used in prior work by [Jin et al., 2021]
(( (s,, a) x3
which is smaller than ours by Jensen's 's inequality.
Our main result stated in Theorem 5.1 below.
Theorem 5.1. Fix any comparator policy with stationary measure μ², we with probability at least 1 28, for any K 2 llog A, Algorithm run iterations with stepsize
we set 3 as in (7), then
1
log A B.
K
outputs policy wou satisfying
2C
log K
J TM <
2B
+ (2]10n"
l1z + 1)( + (9)
T: Tu:Uneertinnty
Te:Optinization
T3 MisMisppeeffiatio
7

---

The upper bound on the sub-optimality gap (9) consists of three terms. The first term Ti represents the uncertainty in the dataset. decays with the reciprocal of the square root of the dataset's size, but increases as the quality of the dataset with respect to the comparator policy degrades, as measured by the coverage ratio. The second term T2 is the error due to optimization, which can be made small by increasing the number of iterations K. The final term T3 is an irreducible error due to model misspecification. Note that the Ta term also decreases as the quality of the dataset improves. Importantly, due to the definition of C' in (8), the bound depends only on the feature dimension d rather than on the size of the state space,
As an application of Theorem 5.1, let us consider the optimal policy n² as the comparator policy л. If || A is bounded above by some constant C., then Theorem 5. implies Ó dede-)) samples are sufficient to learn a policy which is e-optimal up to model misspecification error. One well-studied special case of zero misspecification error is the linear MDP [Jin et al., 2020, Wei et al., 2021]. Under this assumption, combined with Assumption 3.1, we can choose B.,, large enough so that the function class Q( ) contains the true value functions with the knowledge of an upper bound on c. Specifically, if B 2 O(evd), d), a straightforward adaptation of our analysis shows that Theorem 5.1 holds with misspecification error term.
5.1 Comparison with prior work
Our work is inspired by the work on episodic setting [Zanette et al., 2021], particularly the idea of solving constrained optimization problem at each step. This work is also the first to introduce the definition of coverage ratio that we adopt in this paper. However, despite the algorithmic similarities, the algorithm design and analysis in this work rely crucially on backwards induction methods that are only applicable the episodic setting. Our work makes significant contribution by extending the approach to the more challenging infinite horizon setting.
As mentioned in the introduction, the work [Gabbianelli al., 2024] is the only paper are aware of that studies offline RL for average reward MDPs with linear function approximation. However, their algorithm only attains ((e=a) sample complexity guarantees. The main reason for this is their algorithm's s double loop structure. Their primal-dual formulation of the offline RL problem involves solving for the saddle point of a certain Lagrangian objective, which is done through multiple rounds of stochastic gradient ascent-descent. They assume that state action pairs in the data set are sampled i.i.d from fixed distribution. Then in each outer loop of their algorithm, they use O( 2) samples to solve a sub-problem nearly exactly. Since they need ((s-2) outer-loop iterations, this results in a total sample complexity of O( O(E=4). In contrast, in our algorithm the data needed to construct the optimization problem (6) only needs to be sampled once and is then re-used in each iteration. This avoids the inner-loop that uses additional samples. The data re-use creates an additional correlation between iterates which is dealt with in the analysis using covering arguments.
The primal-dual algorithm by [Hong and Tewari, 2024] guarantees O(e-2) sample complexity for discounted MDPs, but their results depend on weaker definition of coverage. Using our notation, their algorithm requires an upper bound on ||ø" 1ن which is assumed to be known. Finally, [Neu
and Okolo, 2025] introduce another primal-dual style algorithm with an O(=-2) sample complexity guarantee for discounted MDPs Their suboptimality bounds depend on ||05*" 12z which is the
strongest result we know of in this setting for the discounted case. The authors mention that would not be difficult to adapt their results to average reward MDPs using the ideas from the work [Gabbianelli et al., 2024], but no additional details are provided. Even so, our work still improves over theirs for two reasons. First, while they use the same definition of coverage ratio as ours, their sub-optimality bounds scale quadratically with this constant in contrast to our linear scaling. Second, their results, like prior work [Gabbianelli et al., 2024, Hong and Tewari, 2024], only cover the more restrictive class of linear MDPs, while we study the more general linear function approximation (cf. Assumption 3.3).
further extension beyond linear models to more general function approximation would be an interesting future direction. In this case, it is not yet clear how one can efficiently construct confidence sets for the underlying parameters. Even so, as shown in [Xie et al., 2021, Cheng et al., 2022], is still possible to implement the pessimism principle with general function approximation. The
8

---

main difficulty we see in adapting the methods from these papers to the average reward setting is the presence of the additional variable ./
Analysis
Let @u(s, a) == ((s, a) we and := (- a)] denote the empirical estimates of qT* and t respectively, at the end of k-th iteration. Key to analysis is the following lemma, which allows us to decompose the sub-optimality in Theorem 5.1 into its three main parts as shown in (9).
Lemma 6.1. Fix policies n, ã E ((A). Let jat be estimate of the true average reward following policy T. and q² E -RSAA A be an estimate of the true O-functionq". Then
J 1 Esruu
[(r(ab)) =(als)) (s.a) ((aA)) 6r ( J q" (0.
Lemma 6.1 is analogous to the so-called extended performance difference lemma, which is commonly used the analysis of optimistic policy optimization algorithms for the online episodic setting: see, for example, the work [Cai al., 2020, Shani al., 2020]. Below break down the analysis into three main steps.
Step 1: Pessimism. Suppose for the moment that (.Q(B..).II = Then by the definition (3) there would exist some wxz such that Φ(s, a) w solves the Bellman equation for policy Ty. meaning that ((s, a) w = (s, a). If we can show that (wi.. Et. _J*)) is feasible for critic's optimization problem (6), we will have Ju I J by the definition of Jk. which has the desired pessimism property. In general though, if (o(B.).I > 0, may be impossible to find such a w Therefore, we instead define
(w k Jk)
arg min
( w J J- T (Ø(:)) " w))m
(10)
B
as the best possible weight vector and estimate of T that incurs at most Ki IIII error by definition.
With the help of Lemma 6.1, we then show that Jx S JE S J + (Q(BB), holds with high probability. This result is summarized in the following lemma.
Lemma 6.2. With probability at least 5, for each k E [K] there exists El. E TRd such that (wL, Ex: Jt) ) is feasible for the optimization problem (6), As a consequence of the definition of Ju-
Js S J S J + KQ(B.). Wk E [K].
Step 2: Bounding the estimation error. The next step is to control the error in the estimates ğR
and Jg. More specifically, in view of the second term on the right hand side of Lemma 6,1, we are interested in bounding
(s.a))) (s.(s, a) + Jr T (s, a)]l
(11)
where æ is some comparator policy. manner similar to step 1, we define
w E arg min [[ w + Ju. T qR lox.
w
which is the best possible regression parameter with target Jn T In this case, we have I] wi Ju T @xll oo S EQ(B_),II by Assumption 3.3. If (Q(B)), 0, then (s, d(s a) we is exactly equal to quantity inside the expectation (11). In the general case, (11) can be bounded by
E (ea)) (s, a) o(s a) will + Eo(
high probability upper bound on the first term above results in the following Lemma 6.3. Lemma 6.3. With probability at least 1 for all [K] and any policy n.
E (( on (8,(s, a) + T (x a)]l s 23 d= 1 + EQ(B.).II

---

Step 3: Completing the proof. Theorem 5.1 holds on the events of Lemmas 6.2 and 6.3, which are true simultaneously with probability least 1 26. The policy output by Algorithm is mixture policy with average reward 5mn Ex J Combining Lemma 6.2 with Lemma 6. we can show
K
K
Jk + (...B.).TTT
K
K
km1
K
E
(mr(als) m=(als))(
K
k=
(sa))r [T (x( Js +
The first term above bounded above by the optimization error, which is proved through the analysis of mirror descent. The proof is completed by using Lemma 6.3, the definition of 3, and rescaling A-1 A
7
Conclusion
In this paper, we have introduced a pessimistic actor critic algorithm for offline learning in infinite horizon average reward MDPs with linear function approximation. Our results show that our algorithm sample efficient, with provable guarantees under only partial data coverage. One limitation of our algorithm is that we require the MDP to be unichain and value functions to have uniformly bounded span. Aside from an extension to general function approximation, potential future work could also include weakening Assumption 3.1 to include all weakly communicating MDPs.
Acknowledgments and Disclosure of F Funding
We thank all reviewers for their helpful suggestions and comments. The research of WP was supported in part by NSF Award DMS-2023239. JK was partially funded by AFOSR/AFRL grant no. FA9550- 18- 18-1-0166. HL was partially supported by NSF Award DMS-2206296. QX was supported in part by NSF grants CNS-1955997
and ECCS-243222
10

---

References
Yasin Yabaaii Peter Bartlett, Kush Bhatia. Nevena Lazic, Csaba Szepesvari, and Gellert Weisz. POLI- TEX: Regret bounds policy iteration using expert prediction. In Proceedings of the 36th International Conference on Machine Learning, volume 97 of Proceedings of Machine Learning Research, pages 3692- 3702. PMLR, 2019.
Akhil Agnihotri, Rahul Jain, and Haipeng Luo. ACPO: A policy optimization algorithm for average MDPs with constraints. In Proceedings of the st International Conference Machine Learning, volume 235 of Proceedings of Machine Learming Research, pages 397-415, PMLR, 2024.
Priyank Agrawal and Shipra Agrawal. Optimistic q-learning for average reward and episodic reinforcement learning extended abstract. In Proceedings of Thirty Eighth Conference on Learning Theory, volume 291 of Proceedings of Machine Learning Research, pages 1-1. PMLR, 2025.
András Antos, Csaba Szepesvári, and Rémi Munos. Fitted q-iteration in continuous action-space mdps. In Advances in Neural Information Processing Systems, volume 20. Curran Associates, Inc., 2007.
Qinbo Bai, Washim Uddin Mondal, and Vanect Aggarwal. Regret analysis of policy gradient algorithm for infinite horizon average reward markov decision processes. Proceedings of the AAAI Conference on Artificial Intelligence, 38(10): 19980-10888 Mar. 2024.
Qi Cai, Zhuoran Yang. Chi Jin, and Zhaoran Wang. Provably efficient exploration in policy optimization. In Proceedings of the 37th International Conference Machine Learning, volume 119 of Proceedings of Machine Learning Research, pages 1283-1294. PMLR, 2020.
Ching-An Cheng, Tengyang Xie, Nan Jiang, and Alekh Agarwal. Adversarially trained actor critic for offline reinforcement learning. In Proceedings of the 39th International Conference on Machine Learning, volume 162 of Proceedings of Machine Learning Research, pages 3852-3878. PMLR, 17-23 Jul 2022.
Ronan Fruit, Matteo Pirotta, Alessandro Lazaric, and Ronald Ortner: Efficient bias-span-constrainee exploration- exploitation in reinforcement learning. In Proceedings of the 35th International Conference on Machine Learning, volume 80 of Proceedings of Machine Learning Research, pages 1578-1586... PMLR, 2018.
Germano Gabbianelli, Gergely Neu, Mattoo Papini, and Nneka M Okolo. Offline primal-dual reinforcement leamnigg for linear MDPs. In Proceedings of The 27th International Conference on Artificial Intelligence and Statistics, volume 238 of Proceedings of Machine Learning Research, pages 3169-3177. PMLR, 2024.
Ilaria Giannoccaro and Pierpaolo Pontrandolfo. Inventory management in supply chains: a reinforcement learning approach. International Journal of Production Economics, (8(2):153-166 2002.
Botao Hao, Nevena Lazic, Yasin Abbasi- Yadkori, Pooria Joulani, and Csaba Szepesvari. Adaptive approximate policy iteration. In Proceedingy of The 24th International Conference on Artificial Intelligence and Statistics, volume 130 of Proceedings of Muchine Learning Research, pages 523-531. PMLR, 2021.
Kihyuk Hong and Ambuj Tewari. A primal dual algorithu for offline constrained reinforcement learning with linear MDPs. In Proceedings of the 41st International Conference Machine Learning. volume 235 of Proceedings of Machine Learning Research, pages 1871 1-77737 PMLR, 2024.
Kihyuk Hong, Woojin Chae, Yufan Zhang, Dabeen Lee, and Ambuj Tewari. Reinforcement learning for infinite-horizon average-reward linear mdps via approximation by discounted-reward mdps. In Proceedings of The 28th International Conference on Artificial Intelligence and Statistics, volume 258 of Proceedings of Machine Learning Research, pages 2989 2997. PMLR, 2025.
Thomas Jaksch, Ronald Ortner, and Peter Auer. Near-optimal regret bounds for reinforcement learning. Journal of Machine Learning Research, 1651):156331600 2010.
Chi Jin, Zhuoran Yang, Zhaoran Wang, and Michael Jordan. Provably efficient reinforcement learning with linear function approximation. In Proceedings Thirty Third Conference Learning Theory, volume 125 of Proceedings of Machine Learning Research, pages 1137-2143 PMLR, 2020.
Ying Jin, Zhuoran Yang, and Zhaoran Wang. Is pessimism provably efficient for offline ri? In Proceedings of the 38th International Conference on Machine Learning, volume 139 of Proceedings of Machine Learning Rexearch, pages 5084-5096. PMLR, 18-24 Jul 2021.
Yujia Jin and Aaron Sidford. Efficiently solving MDPs with stochastic mirror descent. In Proceedings of the 37th International Conference on Machine Learning, volume 119 of Proceedings of Machine Learning Research. pages 499004900. PMLR, 2020.

---

Yujia Jin and Aaron Sidford. Towards tight bounds the sample complexity of average-reward mdps. In Proceedings of the 38th International Conference on Machine Learning, volume 139 of Proceedings of Machine Learning Research, pages 5055-5064. PMLR, 2021.
Gen Li, Laixi Shi, Yuxin Chen, Yuejie Chi, and Yuting Wei. Seuling the sample complexity of model-based offline reinforcement learning. The Annals of Statistics, 52(1):233 260, 2024.
Antoine Moulin and Gergely Neu. Optimistic planning by regularized dynamic programming. In Proceedings of the 40th International Conference on Machine Leurning, volume 202 of Proceedings of Machine Learning Research, pages 25337-25357. PMLR, 2023.
Rémi Munos and Csaba Szepesvári. Finite-time hounds for fitted value iteration, Journal of Machine Learning Research, 9(27):815-855 2008.
Yurii Nesterov and Arkadii Nemirovskii. Interior-Point Polynomial Algorithms in Convex Programming. Society for Industrial and Applied Mathematics, 1994.
Gergely Neu and Nneka Okolo. Offiine RL via feature- occupancy gradient ascent. In The 28th International Conference on Artificial Intelligence and Statistics, 2025.
Thanh Nguyen-Tarre and Raman Arora. On sample-efficient offline reinforcement learning: Data diversity. posterior sampling and beyond. In Advances in Neural Information Processing Systems, volume 36, pages 61115-61157. Curran Associates, Inc., 2023.
Martin L. Puterman. Markov Decision Processes: Discrete Stochastic Dynamic Programming. John Wiley I& Sons, 2005.
Paria Rashidinejad, Banghua Zhu, Cong Ma, Jiantao Jiao, and Stuart Russell. Bridging offline reinforcement learning and imitation learning: A tale of pessimism. In Advances in Neural Information Processing Systems, volume 34, pages 1772-117766 Curran Associates, Inc., 2021.
Lior Shani, Yonathan Efroni, Aviv Rosenberg, and Shie Mannor. Optimistic policy optimization with bandit feedback. In Proceedings of the 37th International Conference on Machine Learning, volume 119 of Proceedings of Machine Learning Research, pages 8604 8613. PMLR, 2020.
Uri Sherman, Alon Cohen, Tomer Koren, and Yishay Mansour. Rate-optimal policy optimization for linear Markov decision processes. In Proceedings of the 41st International Conference Machine Learning. volume 235 of Proceedings of Machine Learning Research, pages 44815-44837. PMLR, 21-27 Jul 2024.
Alexander L. Strehl and Michael L. Littman, An analysis of model-base -ased interval estimation for markov decision processes. Journal of Computer and System Sciences, 74(8):1309 1331, 2008.
Wesley A Suttle, Amrit Bedi, Bhrij Patel. Brian M. Sadler, Alec Koppel, and Dinesh Manocha. Beyond exponentially fast mixing in average-reward reinforcement learning via multi-level Monte Carlo actor-critic. In Proceedings of the 40th International Conference Machine Learning, volume 202 of Proceedings of Machine Learning Research, pages 33240-33267. PMLR, 2023.
Shengpu Tang and Jenna Wiens. Model selection for offline reinforcement learning: Practical considerations for healthcare settings. In Proceedings of the 6th Machine Learning for Healthcare Conference, volume 149 of Proceedings of Machine Learning Research, pages 2 35. PMLR, 2021.
Ruosong Wang. Dean Foster, and Sham M. Kakade. What are the statistical limits of offline RL with linear function approximation? In International Conference on Learning Representations, 2021.
Lucas Weber, Ana Busic, and Jiamin Zhu. Reinforcement learning and regret bounds for admission control. In Proceedings of the 41st International Conference on Machine Learning, volume 235 of Proceedings of Machine Learning Research, pages 52403 52427. PMLR, 2024.
Chen-Ve Yu Wei, Mehdi Jafarnia Jahromi, Haipeng Luo, Hiteshi Sharma, and Rahul Jain. Model-free reinforcement learning in feffintte-hoiizon average-reward Markov decision processes. In Proceedings of the 37th Interna- tional Conference Machine Learning, volume 119 of Proceedings of Machine Learning Research, pages 10170- 10180. PMLR, 2020.
Chen- Yu Wei, Mehdi Jafarnia Jahromi, Haipeng Luo, and Rahul Jain. Learning infinite- average-rewar mdps with linear function approximation. In Proceedings of The 24th International Conference on Artificial Intelligence and Statistics, volume 130 of Proceedings of Machine Learning Research, pages 3007- 3015, PMLR, 2021.
12

---

Tengyang Xie, Ching-An Cheng, Nan Jiang, Paul Mineiro, and Alekh Agarwal. Bellmaan-consisent pessimism for offline reinforcement learning. In Advances in Neural Information Processing Systems, volume 34, pages 6683-6694, Curran Associates, Inc., 2021.
Andrea Zanette, Alessandro Lazaric, Mykel Kochenderfer, and Emma Brunskill. Learning near optimal policies with low inherent Bellman error. In Proceedings the 37th International Conference Machine Learning. volume 119 Proceedings of Machine Learning Research, pages 10978-10989. PMLR, 2020.
Andrea Zanette. Martin J Wainwright, and Emma Brunskill. Provable benefits of actor-critic methods for offline reinforcement learning. In Advances in Neural Information Processing Systems, volume 34, pages 13626-13640. Curran Associates, Inc., 2021.
Wenhao Zhan, Baihe Huang, Audrey Huang, Nan Jiang, and Jason Lee. Offline reinforeement learning with realizability and single-policy concentrability. In Proceedings of Thirty Fifth Conference Learning Theory, volume 178 Proceedings of Machine Learning Research, pages 2730-2775. PMLR, 02-05 Jul 2022.
Yiming Zhang and Keith W Ross. On-policy deep reinforcement learning for the average-reward criterion. In Proceedings the 38th International Conference Machine Learning, volume 139 of Proceedings of Machine Learning Research, pages 12535 12545. PMLR,
2021.
Zihan Zhang and Qiaomin Xie. Sharper model-free reinforcement learning for average-reward markov decision processes. In Proceedings of Thirty Sixth Conference on Learning Theory, volume 195 of Proceedings of Machine Learning Research, pages 5476 5477. PMLR, 2023.
Matthew Zurek and Yudong Chen. Span-based optimal sample complexity for weakly communicating and general average reward mdps In Advances in Neural Information Processing Systems, volume 37, pages 33455-33504 Curran Associates, Inc., 2024.
NeurIPS Paper Checklist
1. Claims
Question: the main claims made the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: The abstract introduction clearly describe main contribution this work, which is an algorithm for offline learning in average reward MDPs with linear function approximation and partial coverage.
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 hy the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can he expected to generalize to other settings.
is fine to include aspirational goals as motivation as long as it is clear that these goals are not attained by the paper.
Limitations
Question: Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification: The assumptions required for our algorithm are clearly stated in section 3, namely bounded Bellman closedness and realizability error as well as unichain MDPs. The paper also clearly discusses the limitation of our algorithm to linear function approximation.
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 separate "Limitations" section their paper.
The paper should point out any strong assumptions and how robust results are violations of these assumptions (e.g.. independence assumptions, noiseless settings, model well- specificcca,,,, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
13

---

model The authors should reflect on the scope of the claims made, e.g., if the approach was only tested a few datasets with few runs. In general, empirical results often depend implicit assumptions, which should be articulated.
The authors should reflect the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because 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, worse outcome might that reviewers discover limitations that aren't I 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.
3. 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]
Justification: All assumptions are stated in Section 3. A rigorous proof of the main theorem is given in the appendix.
Guidelincs:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should he numbered and cross-referenced.
All assumptions should be clearly stated referenced in the statement of any theorems.
The proofs either appear in the main paper the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide a short proof sketch to provide intuition.
Inversely, any informal proof provided in the care of the paper should be complemented by
formal proof' provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental result reproducibility
Does the paper fully disclose all the information needed to reproduce the main experimental results of the paper to the extent that it affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Question:
Answer: [NA]
Justification:
The paper does not include experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data provided or not.
If the contribution is dataset and/or model, the authors should descrihe the steps taken make their results reproducible verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, the contribution novel architecture, describing the architecture fully might suffice, or if the contribution is a specific model and empirical evaluation, it may be necessary to either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g., in the case of a large language model), releasing checkpoint, or other means that are appropriate to the research performed.
While NeurlPS does not require releasing code, the conference does require all submissions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
14

---

(a) If the contribution is primarily new algorithm, the paper should make it clear how to reproduce that algorithm.
bb) If the contribution is primarily a new model architecture, the paper should describe the architecture clearly and fully.
(c) the contribution a new model (e.g. a large language model), then there should either be a way to access this model for reproducing the results or a way to reproduce the model (e.g.. with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, which case authors are welcome to describe the particular way they provide for reprodueibility. In the case of closed-soure source models, it may be that access to the model is limited in some way (c.g.. registered users), but it should be possible for other rescarchers have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access the data and code. with sufficient instructions faithfully reproduce the main experimental results, described supplemental material?
Answer: [NA]
Justification: The paper does not include experiments requiring code.
Guidelines:
The answer NA means that paper does include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (bttps://nips.co http://iippccc/ppttp cc/public/ guides/CodeSubret ssionPolccy) for more details.
While encourage the release of code and data, understand that this might not be possible,
so "No" acceptable answer. Papers cannot rejected simply for not including code, unless this central to the contribution (e.g.. for a new open-source benchmark).
The instructions should contain the exact command and environment needed the results. See the NeurlPS code and data submission guidelines (https: //tp://iiissaeeee cc cc/public/ guides/Codes Stte//CooSSuuiiiseeeeeeee soniiisssoopoiooooo for more details.
reproduce
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 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.
6. 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 understand the results?
Answer: [NA]
Justification: The paper does not include 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 level of detail that is necessary appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, supplemental material.
7. Experiment statistical significance
Question: Daes the paper report error bars suitably and correctly defined or other appropriate informa- tion about the statistical significance of the experiments?
Answer: [NA]
Justification: The paper does not include 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.
15

---

The factors of variability that the error bars are capturing should be clearly stated (for example. train/test split, initialization, random drawing of parameter, overall run with given experimental conditions).
The method for caleulating the bars should he explained (closed form formula, call library function, bootstrap, etc.)
The assumptions made should given (e.g., Normally distributed errors).
It should be clear whether the error bar is the standard deviation the standard of the mean.
It is OK report I-sigma error bars, one should it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality crrors 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). 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, docs the paper provide sufficient information the computer resources (type of compute workers, memory, time of execution) needed reproduce the experiments?
Answer: [NA]
Justification:
The paper does not include experiments.
Guidelines:
The answer means that the paper not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory
storage.
The paper should provide amount compute required each the individual experimental runs as well as estimate the total compute.
The paper should disclose whether full research project required more compute than experiments reported in the paper (e.g.. preliminary or failed experiments that didn't make into the paper).
Code ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurlPS Code of Ethics https://neute:
cscuideliee?
Answer: [Yes]
Justification:
We have reviewed the NeurlPS Code Ethics and verified that our paper conforms with
it.
Guidelines:
The answer NA means that the authors have not reviewed the NeurlPS Code of Ethics.
the authors answer No, they should explain special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (c.g., if there is a special considcration duc to laws or regulations in their jurisdiction).
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: This paper is theoretical in nature and not directly related any practical application with potential for societal impact.
Guidelines:
answer means that is no societal impact of work performed.
the authors answer NA or No, they should explain why their work has societal impact why the paper does not address societal impact.
Examples negative societal impacts include potential malicious or unintended uses (e.g.. disinformation, generating fake profiles, surveillance). fairness considerations (e.g., deploy- ment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
16

---

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 out. For example, 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 train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used intended and functioning correctly, harms that could arise when the technology is being used intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
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 monitor- ing misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper describe safeguards that have heen 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)?
Question:
Answer: [NA]
Justification:
The paper poses no such risks.
Guidelines:
The answer NA means that the paper poses such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards allow for controlled use of the model. for example by requiring that users adhere usage guidelines restrictions access the model 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 take this into account and make 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: The paper does not existing assets.
Guidelines:
The answer NA means that the paper does not 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 URL.
The name of the license (c.g., CC-BY 4.0) should be included for each asset. For scraped data from particular source (e.g., website), the copyright and terms of service of that source should be provided.
If assets are relcased, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswi wwwwwtthhcdee... com/ /dntaaat has curated licenses for datasets. Their licensing guide help determine the license dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it changed) should provided.
this information not available online, the authors encouraged reach out the asset's creators.
13. New assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification: The paper does not release new assets.
Guidelines:
The answer NA means that the paper does not release assets.
17

---

Researchers should communicate the details of the dataset/code/mooel as part of their sub- missions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent obtained from people whose asset used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL. or include an anonymized zip file.
14. 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: The paper does not involve crowdsourcing rescarch with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing 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 much detail as possible should included the main paper.
According to the NeurlPS Code Ethics, workers involved data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional review board (IRB) approvals equivalent for research with human subjects
Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Question:
Answer: [NA]
Justification: The paper does not involve crowdsourcing research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing rescarch with human subjects.
Depending the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. you obtained IRB approval, you should clearly state this the paper.
recognize that procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurlPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applica- ble), such the institution conducting the review.
16. Declaration LLM usage
Question: Does the paper describe the usage of LLMs if it is important, original, non-standard methods in this research? Note that if the LLM used only for writing, editing, or formatting purposes does not impact the core methodology, scientific rigorousness, or originality of the research, declaration is not required.
component of the
Answer: [NA]
Justification: The core method development in this research does not involve LLMs as any important, original, or non-standard components.
Guidelines:
The answer NA means that the core method development in this research does not involve LLMs any important, original, non-standard components.
wwtp///ofeeeecce///2///////////e for what Please refer our I.I /ttp/////////////rrrr/ee//////// should should not be described.
18

---

A Further Discussion of Assumption 3.1
Here give a more detailed discussion of Assumption 3.1 and how it compares other average reward MDP models used in the literature.
The weakest assumption frequently made is the requirement that the MDP be weakly communicating [Jaksch al., 2010, Fruit et al., 2018, Wei et al., 2020, 2021, Zhang and Xie, 2023, Hong et al., 2025, Zurek and Chen, 2024]. Aside from [Zurek and Chen, 2024] who study learning with access to generative model, all of the works cited above study online learning in weakly communicating MDPs. We are not yet aware of any papers studying offiine learning in weakly communicating MDPs
An MDP is weakly communicating if the state space can be divided into two classes. One class consists of states that are tramsient for every policy. The other, called the communicating class, consists of set of states with the following property: for each pair of states (s, s') there exists a policy x such that s' is reachable from when following [Puterman, 2005]. As shown in [Jaksch et al., 0), the weakly communicating assumption is necessary for efficient online learning. The property of being weakly communicating is sufficient to guarantee the existence of a solution (q" J") to the Bellman optimality equation
('( a) + J' r(s,a) a) E( [maxq" (s', as',a)
where J is constant. However, this is not enough to guarantee that for a fixed policy n. (s) as defined in (1) is constant. In this case, solutions q" to the Bellman equation
q (s(,,a) + T"")""""''("s (s,,a)
= T"
may exist, but may only be unique modulo subspace of dimension greater than one. This is because, in weakly communicating MDPs, there can be policies that induce Markov chains with multiple recurrence classes. As such, the chain's 's stationary measure is unique: there different one for each recurrence class. Moreover, while q" bounded, there is no guaranteed uniform upper bound on the size of 9" as opposed to discounted and episodic MDPs where 1 style algorithms difficult. It is not clear how to accurately estimate q= a) in the weakly communicating case, and lack of a clear upper bound can destabilize the algorithm.
I-n or H provide a natural upper bound. This seems to make learning with policy optimization
At the other end of the spectrum, the strongest assumption made in the literature is uniform ergodicity. The "ergodicity" part of this assumption requires that each policy induce irreducible, aperiodic Markov chain. This ensures that the stationary measure unique for each policy and positive everywhere. The "uniform" part of this assumption means that that worst case mixing time
mix = sup in 2 1 max][(P)) (s, - p² llr < 2)
(12)
5
is finite and all stationary measures are uniformly bounded away from zero:
inf f (s) 2 a > 0.
(13)
When learning with linear function approximation, this second condition is often replaced with
E( @e (0ss, a) (o(s) a)
> AI,
(14)
meaning the true covariance matrix for each policy is uniformly positive definite. This is referred "uniformly excited features" assumption in [Wei et al., 2021, Hao et al., 2021].
the online setting, uniform ergodicity has been assumed in e.g. [Abbasi- Yadkori et al., 2019, Wei al., 2020, 2021, Bai et al., 2024j. Under this assumption, the Bellman equation is solved by
(s, Σ E., (r(se, oc) - (
J==
(15)
and (g" S O(taxx) This is convenient for online learning, especially with policy optimization, because the functions are bounded and (13) and (14) imply that each policy is self-exploratory.
In the offline setting, assumptions such as (13) and (14) would greatly weaken single policy coverage results such as our Theorem S. As discussed in the main body, effectively covering any policy requires covering the entire state space in the case of (14) or the entire feature space in the case of (14).
Because of this, it important for to emphasize that our assumptions do imply conditions such as (13) or (14). Our Assumption 3. which is the same assumption made by [Gabbianelli et al., 2024], can be thought of as being somewhere in the middle of the two extremes mentioned above. It a stronger than weakly communicating, but weaker than uniform ergodicity. Indeed, the uniform mixing condition (12) by itself implies Assumption 3.1 but is not necessary. Another sufficient condition is the existence of single state visited in
19

---

0.4
0.6
0.6
0.4
2
Figure I: Two state river swim model. The dashed edges represent transition probabilities when taking action and the solid edges show the transition probabilities when taking action
expected time at most h started from any other state as assumed in [Agrawal and Agrawal, 2025]. With this assumption, the span of the q- g-function bounded by h.
We end this section with simple example of MDP which satisfies Assumption 1.1 but is not uniformly ergodic. Figure 1 diagrams simple two state river-swim [Strehl and Littman, 2008] MDP where S = {1, and A = [L., R3. Conditioned on heing in state 1, the agent stays in state almost surely action T. chosen. action R is chosen, the agent will stay in state with probability 0.4 and transition to state 2 with probability 0.6. On the other hand. if in state 2, the agent deterministically transitions to state I if action L is chosen and will stay in state with probability 0.6 if action It chosen. Otherwise, it transitions to state 1. A simple linear algebra computation shows that the stationary measure given by
0.6 1 + 0.6( T (R(2)) 1 0.6( (R1) π (R2)))
0.67 (.67(
1 (1),
for any æ. If the agent never takes action R state 1, i.c. x (( then n "²( is also easy to see that expected covariance matrix,
so condition (13) fails.
(14), rank and so cannot be positive definite d 2 2. However, it is not hard to show that for any initial distribution v and policy x,
1(uPr)++
()) n= (i) s 0.6((u xT)())
for j E (1, This gives upper bound on faux q².
llg 2
which by (15) implics an upper bound on the span of
B A Fully Computationally Efficient Implementation
As discussed in Section 4, Algorithm as written the main body not fully computationally efficient. This because Line 5 assumes that the parameters (wy, Eu Ja) are an exact solution to the optimization problem (6). It is not guaranteed that an exact solution to this problem can be computed efficiently. However, approximate solutions to (6) can be computed in polynomial time using interior point methods [Nesterov and Nemirovskii, 1994]. In this section, we briefly show how a fully computationally efficient implementation of Algorithm where (6) is solved only approximately in step 5 results only in a small additive error proportional to the accuracy of the solution.
Specifically, for some tolerance parameter > O, let us assume that (wL,, Ju)) are a r) r-aappoximmae solution (6). This means that Ju is within 7 of the optimal solution and the magnitude of the constraint violation most 7) when measured in the norm. Then the inequality Lemma 6.2 may updated read
Jk S J + S T #o((B)) +
The error in the constraint violation will appear in Lemma 6.3. If we approximately solve (6) so that (we, Exy Ju) satisfy
N
wi Es A-1
" disi, as) (r(s,,a)) J + (x(())) wx ST.
[J&| S 1 +
Iwell22 S Bu + and || S 8
then a quick inspection of the proof of Lemma 6.3 (more specifically Lemma C.3 below) shows that the result can be updated to read
E( (+x (s, a) + J4 - T qu a]]l & 2(33 + "))l""" ll + +eQ(Bu). + +.
Altogether, this only results an additional error
2n ll 1 2n
added to the right hand side of (9) in Theorem 5.1.
20

---

C Proofs of Key Lemmas and Theorem 5.1
In this section, we will prove the key Lemmas from section and also give a rigorous proof of Theorem 5.1. We start with Lemma 6.1.
Proaf of Lemma 6. I. Define 8* (*(s) - E, #(als}q (s, Adding and subtracting r(s,a) J + Pa and then using J ( @* []] we have
Ex-ueT Σ (aal))a"(
Σ nt(lls) (4 (x, -r(ss,,))
r((,,) Pra
Σ x(aas)) (r(s,u) j j + P)o
Exruee
B(x.))-u= (8, (s, + T (() + + J Bla ox Pas
Now, since μ²" is the stationary measure for policy n
(Ga P
Basny (6 (s)] Bawu
Σ #(als){ (s,
Inserting this into the last line above and re-arranging completes the proof.
C.1 Proofs Lemmas 6.2 and 6.3
Before proving Lemmas 6.2 6.3, we need introduce some additional notation one auxillary result. Define the restricted policy class
11(Ba)
En edia ||01|2 S Be
and the value function class
VBB, Bw) = (u(3;)) = (TT(1ss, q(s, x II(Bo), q Q(B.))
(16)
The number Be represents the maximum size of any policy parameter 0s used during the course K iterations of Algorithm 1. Notice that, based on the policy update in Algorithm we have
100l12 S
wull2 S n.B.
so take Be B..
The proofs Lemmas 6.2 and 6.3 rely on the following uniform concentration inequality. proof is based on standard arguments from the literature first used in [Jin et al., 2020]. The proof of this lemma delayed to Appendix D.
Lemma C.I. Let {uu)k_n be any, possibly random, collection from the function class V(Ba, B..). With probability at least - 8 we have, for all & [K].
Σ ((s an) (Po..s Uh - v2((())
S ST² N,5,
1-1
where
(B,, = 1B2 ( log
K(N [)
+ dlog(1 + ANB.) + dlog(1 + 16N 16N BB) 8.
We define C, the constant that appears in (8),
C = T(B.. N, K, + B.,
The constant I' is derived from the well-known comcentration of self normalized processes (Lemma E.4) and the log cog-covering number of the class VBB, Bw).
The next lemma shows that J defined in (10) within ko(R.).. of TM
21

---

Lemma C.2. Under Assumption 3.3 we have
jJz J S (.(
for every E [K]
Proof. Let (s) = ((s,a) aaaa)"un "[ By Lemma 6.1 and Assumption 3.3
1 JKl = (( (o (s. a) + Ji 42
< ll + Jk - - 20
We are now ready to prove Lemma 6.2. Throughout the proof, let
qil(s, u) = c(5 a) wi (x) Eawe (1)) (x.
be the approximate y and value functions corresponding to the optimal parameter wj.
Proof of Lemma 6.2. By the definition (10), wi and Jr are always feasible variables. Thus, we need show that there is some E Re with || S B such that
wi = +
Σ (ss., (r(s):a:) 1x (5') wii
To this end, note that
wh Å Rwy
A (ss, a;)00;;; (s)
+ A-''i
N (s,, a:) ( (s, 1 A Σ
A
o(s,, ass,, + wt. (17)
where define
(s a) = qلl () J -
Adding and subtracting ef (5.) from the first term in (17) have
N
A
Σ (88 a.) (T gi (sc, -J)
os, as) (r(s;, as) - St vs()) + À + Σ pls,, as) (Pa,,, -(x(s))
Now (s.) Bn (12)) = (st) wi. So, plugging this back into (17) we have
N
wi = + 1 Σ a.) (r(s), - J2 0²* =x (s.) we)
where
E. -
0(81, (P) v((s()) + A Σ pss, (s a:) + -
(18)
To complete the proof, we only need to show that || for all & [K]. by Lemma C.1 we have
holds with high probability. Since of V(B Bo)
(81, (Po.Pa -z(()))
Σ (ss, (P). "i - vz((1))
=
r(B., N, 8, K,
22

---

holds for all & with probability at least - 6. Next, using the projection bound, Lemma E.3, and (s, a:)l S x)(B=).1 implied by Assumption 3.3, have
A
bas as Ae,s, ai) S S
Finally, since À 3 I,
||A- wi i i
| /wwill S Bw.
Therefore, by (18) and the triangle inequality,
|| S [ 6, K, Ko + B S.
holds with probability least 5. The proof is complete.
We now move on to the proof of Lemma 6.3, Recall
(x(s) = E ((x
as the definition of the empirical value function estimated by the critic. Since 0a(s)
(**(s) we. it follows
from the definition of (Jz, wk, Ex) as the solution to the optimization problem (6) that
we E. + A
Σ S(su, (.)((s) Ja En (s()).
(19)
We will need the following statement. Lemma C.3. With probability at least for each k E [K] we have [B(r,)) (0, Φ(s,a) wxll 28110"1
for any probability measure μrr E ASS A). Proof.
For this proof, we define
We + Js T (8, As(s,a) = c( =(0))==)))aa))
We observe that
Th Ả Amo
A Σ (ss (.)(s,)))) wx + +A* A- "
Σ ((8,, a, )T (.) Ju) + A Σ (ss a(ss, + A wwx.
Using (19), allows us to write the difference in the parameters wy and T as
WL - wh = Ee A
as. a:) (r(ss, - Ju + +x(())) A ols (I - (k)
S (( - -A-1
E. A-
(s, a:) (ūx(el) Paya, - A-1 Σ
Msn as) An),a)) --'wo we.
So we have
N
6(s,a) a) (wa (ww
wx) o(s,a)) Es a(s,a) -A-1 Σ ((s) P
((s,a) T Σ
TA -' (sss,a)) o(s.a) A
wo..
23

---

Denote of = (ola))u(((ss a)]. Taking an expectation followed by an absolute value we get
((xa))uljuss,d) o(s, a) wxl] = 1(d")) (wx m0n)
N a(ss. (=)(((()()) Pagin; 0x)
s ((dd))Eel
(0")TA-1
(20)
+ (00)
E ois ai As + 1((0") ( 'wkl
Let consider each of the above terms the right hand side. First, have by Holder's incquality
(( " Eul s l1 11 1l6xll $ 81lø"1la-1
where the second inequality due to the constraint || S 3 the optimization problem (6), For the second term, using εx E V(Bw, Bb) for all k, we appeal to Lemma C.1 to get
(0))
oss (Bu((s) - Par.ar 8x)
S 1
Σ o (.)((s)))))))))))))))))))))))))) -a Pa 8u)
A
ST(Bw, N, K, |
with probability at least for all k. For the third term, we use (s a)) S E by Assumption 3.3 and Lemma E.3 to get
(0)) (0))
Σ ((s, (s)
s 11
Σ o( a.) as)
X-1
S ( N|
Finally, for the last term on the right hand side of (20) we simply observe that
((0")_ À wx S ||ø" (o=lla- 1 ||ø | Bulld 12-1 Combining everything shows that with probability least 1
(0x a) wx]1 s (8 ( I(Bu, B, d, EQ(B.)..V Bio) 11 lla-
x 23110"11>-1
as desired.
Proof of Lemma 6.3. Adding and subtracting á(s, a) T.. we can decompose the Bellman error into two terms
á (8) + Jn - T (s, T = Ga(s, (ss, a) + á(s,a) wi + J. T (s)
Therefore, by Lemma C.3 and the definition of w..
E
+ fr T qu(s, a]]l & 8 (Tu(s, b(s, a) "ewl
+ +[|0(.-) wa Js 7 = g0lloo
s 23| 1la (Q(B.).
C.2 Proof of Theorem 5.1
We ready prove Theorem 5.1. We will need the following Lemma analyzing the actor's optimization procedure.
Lemma C.4. Fix comparator policy π E A(A). We have
Eswuy
E
K Σ (m(ass)
(cls)) I 2B
log A
K
Proef. Notice that the policy parameter update in Line 7 of Algorithm can be written as the exponential weight update
Tk+1 Tkls(a)s) TA (als)) exp (ngu (s. a)).

---

We have l6x (s, a]] = ( s) wk Σ B.. by Algorithm I's constraint and the normalization of d(s, a) in Assumption 3.3. We then appeal standard analysis of exponential weights (Lemma E. If choose ry S Bw then conditions of the Lemma E.1 are satisfied and we have
K
log (m(aas) [=(cls))(uss.))>
R Σ
==(a)s](a(s.a))
7
k=1nEd
log A
"
We choose
log A KB
which is S P whenever K 2 log A. get
Σ (T(ass) - ma(a))))(())))) 2 v log A.
The proof completed by dividing both sides by K, and taking an expectation with respect to 8 ~v p²"
Proof of Theorem 5.1. We work on the events of Lemmas 6.2 and Lemma 6.3 which, by union bound, hold simultaneously with probability at least - 26.
By Lemma 6.1 we have
K Be ((T(a)s) (x)
3
Σ
qu 3s Qu a))
K
k=1
By Lemma C.4, the first term the right hand side bounded by 2B v
Aog K
For the second term, by Lemma
6.3
Baaa)aa Gn (e) - -a-- (s, S
Σ
2, lla-1 + +EB..BB)
K
= =2,110" 1 + E BB.
We next observe that Lemma 6.2 implies
K Σ
K S Ju KBw.
1=1
k=1
log A
<
2B
2/ ll 1 + BB. + K B...Bg
K
To complete the proof, we use the definition of 3 and replace Å with 1 3Ax!
D Proof of Lemma C.1
This section is dedicated the proof of Lemma C.I. We with the following general result whose purpose be to show that policies are Lipchitz continuous parameter This similar to what is done [Sherman et al., 2024].
Lemma D.I. θ C Idd a convex set and {fo : 0 O} be class of parameterized functions from gd Suppose that map + fo(x)) is continuously differentiable and that supzeze weteeeeeeeeaaaeeeellllloooeo Voforz)) $ for some constant L.. Then for any 0z, 02 E O and E S,
[| (-|s) Taz (-15)]1 2L 02l12
where
coo(o(aa))
To (a(a))) Enr elolo())))
and 6(s, a) in Assumption 3.3.
25

---

Proef. Note that
sup (s
[Vofo(p(s, a))ll2
since a)]l under Assumption 3.3. Fix 01, 02 and state S. Let
[A] and let
Veto((alss)
Jo(s)
Voro(amls))
be the Jacobian of + (-(s))). straight forward computation shows that
Vamo(als) = no (a s) Vofolá(s,a)) - Σ Vefoló(s, (oolaalss)
(21)
Fix & E [0, 1] and define 0, (1 - 1)01 + 102. Let J, 02 be the matrix fo Jo, dt. Then by the fundamental
theorem of calculus
|o (-1s) - To, (-1=)]1 = [|Jo, (01 02)111-
Now let a be fixed. Using (21), we can bound the absolute value of the a-th entry of the vector Jo1.o2 (0: 02)
//-0 (als (01 -aa)
(Je,,0, 0z (0) -O2)al
% no, (als) Σ VoJa a')" 0O) (a'ls)
$ 1/- Te, Valu
02)ldlt
L (al(s)
(ofo, (0: To (dlls)dt
$ [.| 021l2 /'' To. (als)at + 1 02112 //" no, (als) Σ no, (a'ls)dt
2T. [0 02ll2 J. To. (als)at
where the second last line we used Cauchy-Schwardd Schwartz [[Vof((((s S L. Therefore
|| (-1s) ne, ==,(-ls) (-1s)]1 = Σ Jo 02)al & 221110, 02l12 Σ ne, (als)dt 2L 022122
Lemma D.I can be applied the restricted policy class II(B,) by taking O be the d-dimensional Euclidean ball of radius Ba and the family (.e 0 } to be the set of functions (á = Φ 0 where ||øl|2 S 1. Clearly, we have [oJo(e)lla & 1. Thus, Lemma D.I shows that
|| (-18) - (11()1)) s 2||0: - 02112
(22)
for all me, ne, II(B)).
With this we can now bound the e-covering number of the function class V. Lemma D.2. Let be the function class (16). Then
log NzV) < d d'log (1 - 4Bw/e) + d log (1 + 16B Be/E).
where N:VV) is the e-covering number of with respect to the norm Il
Proof. First, consider two functions q(: ; w) and q(+, ; w') Q(Bw). Using the normalization in Assumption
3.3
ig(s, 0; w) a = ((0(s, a), w'Yl S || w 1|2
26

---

for any a). So for fixed policy II( we have
lo(s; n, w) v(s; TT, w
max Σ a(
2(8, a, w'))
S max a( w)
s,0
w w' w'll2.
On other hand, fixed w. separate policies ne, Ter E 11.
[,,s, w) n(ss n w))
S max Σ (To(aas)) नer (als))))(
- Bu max [(o() Ter (-1+)]l1
< 4 11
where the second line used 1q(s, a); w)) m(,, n', w/) E II,
By and the last line used (22). Thus it holds for any n(s n, w))
[u(s, n., w) - u(s w')
I lu n, w) - v(s, w')l + (o(s, x, w') - v(s, x',,,",w")) | w' ||2 4B... 6' ||2.
(23)
Now, using standard result concerning the covering number of the d-dimensional Euclidian ball (Lemma E.2), we can construct & covering of the euclidean ball d-dimensional euclidean ball of radius By with cardinality most (1 + fe) and an sB. covering of the Euclidean ball of radius Ba with cardinality not exceeding ,, Be))/ Let V. be the members of V parameterized members (w', 0*) of the Cartesian product of these coverings. Then
Ng() log [Vl & dlog (1 + AB + dllog (1 + 1.B.,.
and by (23), for any o(; To, w) E V we can find v(: Ter, w') E V. with
(n(s; w) v(s, mer w/ ) s |/0 w |22 4 4B 10 0'
E $
+ 4B 8B..
2
Proof of Lemma C.I. Fix (ur C V(Bu, Bo) Appealing to the uniform concentration of self normalized processes (Lemma E.5) and using that |/ullo S Bu for any v E V we have, for fixed l.
((N+1) 1) + +oggNo(13) + 8
Σ ((ss, ai) (Po vu(ss))
s 4B"
log
5
À-1
holds with probability 1 &. K. becomes
Ne (V) from Lemma D.2, the upper bound Now. substituting the bound for No
K(N ((N+11) + dllog(1 + 4B.//e) + d'log(1 + BaB...//s)) 8.222.
4B2 log
Taking 1/N followed by union bound for over it 1,..., K complete the proof.
E Auxiliary Lemmas
Lemma E.I. Let (Xa]a21 be sequence of vectors in RA. Set mI (a) for all E A for each k 2 2,
Tk+ Te (a) (()(
Evee (a xxp(1
for some positive stepsize n satisfying ()x((a) 2 for all and A. Then for any fixed n" e A(A).
log A
Tt The Xa) <
Ta)a)
27

---

Proef. Define Z4 = Eoo'sd EA Tx(aa) (xx())xxxxxx( Then using the inequality e" < 1 x x² which holds
for all x S followed by log(1 + x) S x we have
log Zx log Σ
Tx(a') mx(d)))x((xxx(())
log
1+
Σ
Ta(a)nXe(a) +
Σ
n'EA
aEd
aEA
I Σ
Tu(a)Xu(a)+1) Σ
Ta(a)
aEd
Thus,
(a)
(a TT)
DX [[++)))- P (x)) E (a) log
Σ
x (a)
T++1(a)
aed
aEA
(a) expl exp(-nXx(a))
π (a)
Σ x (a) log
Σ (a) log
(2(a)
Tx((a)
aEA
aEd
log Zx 11 Σ (a)ax{((a)
aEd
1
Σ (x) +1 Σ
Tx(a)xx(a)² - Σ x'(a)xe(a).
aEA
aEA
aEA
Rearranging and summing from l: to K,
(a) ma(a))xa(a) S Σ (KL(x"Ilmm) P (x(a)xx(aa*
REA
REA
- Dkz(F")|m1) n
Tu(a)
Since Ti (a) A for all o.
(Ag Dodtr S log A.
(KI(TT|IAI)
aEA
Plugging this bound in above and dividing both sides by v we complete the proof.
Lemma E.2 (Covering Number of Euclidean Ball). For any 0, the e-covering number of the Euclidean ball Rd with radius R is upper bounded by (1 (1+2M) 2R/e)
Proof. See [Jin et al., 2020] Lemma D.5.
Lemma E.3 (Projection Bound). Let (0i))21 be sequence in Rd with [1bll2 S and {a:b121 be sequence real numbers with la] A. Define
A. Σ dio + I.
We have
Σ a.p 1m1
S AAn.
A-
Prouf. See [Zanette al., 2020] Lemma 8.
Lemma E.4 (Concentration of Self-Normalized Processes). Let (X+); be real-valued martingale difference sequence adapted to filtration (Fi),- Suppose X, o-subgaussian conditioned on F. i.e.
0²
log B
AX [F.
Let (dr)s be RR valued predictable process. Assume Ao axd is positive definite and let As Ao Di= b. Then for any 5 > 0, with probability at least 5 we have
(det(Ar)de((Ao))
Σ b.X,
20² log
N-1
28

---

Proef. See [Jin et al., 2020] Lemma D.3.
Lemma E.5 (Lemma D.4 [Jin et al., 2020J). {21) be stochastic process on state space with corresponding filtration {Fe)ie)- Let { be an valuud stochastic process where Φr Fi-1 and
|| < 1. Let As Eim debi Then any 8 >> O, with probability at least 1 - 5, for all k 2 0, and any V E V so that [ I H, we have:
Σ Φe (V()) (()
4H2
1/2
d
log
A:
+
+ log
Na0l)
+
8K"E"
A
A,
where N₂ is the e-covering number of V with respected to the distance disi(V, V, V*) = sup, (V(2) V'(x).
29


Reviews:
[{"review_id": "3jV6mhWu9R", "reviewer": "Reviewer_wWmr", "summary": "The paper proposes a pessimistic actor–critic algorithm for offline reinforcement learning in infinite-horizon average-reward MDPs (AMDPs) with linear function approximation.\n- The critic obtains a lower-bound (pessimistic) estimate of the average reward and its policy gradient by solving a single linear program with convex quadratic constraints that represents the fixed-point Bellman equation, avoiding the step-by-step regressions common in episodic settings .\n- The actor performs a conservative policy-improvement step on a soft-max policy class. Repeating the alternation $K$ times and outputting a mixture of intermediate policies yields an $\\varepsilon$-optimal policy (up to model-mis-specification error) with sample complexity $O(\\varepsilon^{-2})$—the first optimal-rate result for offline AMDPs .\n- The theory relies on (i) unichain dynamics with bounded Q-span, and (ii) approximate realizability + Bellman restricted closedness of the linear feature class .\n- Compared with the only prior provably efficient offline AMDP method, PDOR, the new algorithm improves the ε-dependence from $O(\\varepsilon^{-4})$ to $O(\\varepsilon^{-2})$ and removes the need for exact linear MDP structure .", "questions": "The conclusion suggests extending to “general function approximation.” What obstacles prevent directly replacing the linear critic with a neural network trained by convex-constrained regression?", "limitations": "yes", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "# Strengths\n- Rigorous proofs culminating in Theorem 5.1 with explicit finite-sample bounds\n- Clear comparison against prior rates (PDOR, discounted-setting results).\n-  Tackles the average-reward offline regime, important for continuing tasks (inventory control, admission control) where resets are impossible\n- Optimal-rate guarantees were missing in this setting.\n\n# Weaknesses\n- Results hinge on linear approximation\n- Pessimism paradigm already popular in episodic/dis­counted RL", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the positive feedback.\n\nThe main obstacle in directly replacing the linear critic with a neural network is the method we use to enforce pessimism. Specifically, the variable $\\xi$ in (6) is constrained to a confidence ellipsoid $\\lVert \\xi \\rVert_{\\hat{\\Lambda}} \\leq \\beta$. The parameter $\\beta$ quantifies the uncertainty in the dataset. This is determined precisely using martingale concentration results from the linear MDP literature. It is not yet clear how to extend this technique to more general models such as neural networks.\n\nThere are methods in the literature that implement pessimism for more general approximation. However, they need to sacrifice the precise uncertainty quantification that can be achieved in the linear setting. Two relevant papers mentioned in the related work section are those of [Xie et al., 2021] and [Cheng et al., 2022], which focus on the discounted setting. Algorithm 1 in [Xie et al., 2022] alternates between policy optimization steps and a critic which chooses a pessimistic approximation model from a general function class. When specialized to the case of linear function approximation, their algorithm can be viewed as solving a Lagrangian relaxation of a constrained problem similar to ours, but with only the linear constraint. Since they work with more general function approximation, they are not able to quantify the uncertainty in the dataset to the same level of precision as we are in our paper. Instead, the amount of pessimism is determined by the Lagrange multiplier, which is a tunable hyper-parameter. The algorithm is very general, but when specified to the linear setting, the lack of precise uncertainty quantification results in convergence rates of only $N^{-1/3}$ for $N$ data samples. \n\nIt would be interesting to see if similar ideas work for average reward MDPs, but it does not seem trivial due to the presence of the additional variable $J$ in the average reward setting. We leave these interesting questions for future work."}, {"review_id": "Q7zUfhgoQo", "reviewer": "Reviewer_oazj", "summary": "The authors propose an actor-critic method for efficient offline RL in average reward MDPs with an intractably large or infinite number of states. They consider the linear function approximation framework, and make assumptions on the expressivity of their function approximator including approximate $q^{\\pi}$-realizability and Bellman completeness under any policy. Inspired by the actor-critic algorithm of Zanette et. al [2021] for the finite-horizon setting, for steps $k=1,...,K$ their algorithm obtains the critic’s weight $w_k$ as the solution of an optimization problem, then updates the actor parameter $\\theta_k$ such that the resulting actor policy in any state is equivalent to one step of mirror-ascent with KL regularization and critic evaluation $\\hat{q}_k(s,\\cdot)=\\langle \\phi(s,\\cdot),w_k\\rangle$ as the gradient. Similar to Zanette et al [2021], their optimization problem is constructed in each step using samples from the offline dataset, and constrains the critic weights to be equivalent to the perturbed solution of a ridge regression problem – with the sample estimate of $q^{\\pi_k}$ as the target. Furthermore, in the absence of the backward induction property enjoyed by finite-horizon MDPs, and the presence of the cumulative return $J^{\\pi}$ in the Bellman expression of $Q$-functions in the average-reward MDP setting, they propose two modifications to the optimization problem: 1) a new decision variable $J$ to estimate $J^{\\pi_k}$ and 2) a direct parametrization of an estimator for the state-value function $v^{\\pi_k}$ based on the critic’s weights. With these modifications, they prove $O(\\varepsilon^{-2})$ sample complexity guarantee under the weakest known data collection and coverage conditions. Precisely, they do not require that the dataset is generated i.i.d or by a single behaviour policy, and they only require the dataset to properly cover a single direction in the feature space. Their sample complexity guarantee also scales linearly (rather than quadratically) with the coverage parameter.", "questions": "I have just one question:\n* Do the authors assume that the initial state is fixed?\n\nSome typos:\n1. L286: “However, their algorithm’s...” should be “However, their algorithm...”\n2. L299: “...while we study the more general function...” should be “...while we study the more general linear function...”\n3. After L335, the second inequality: $(s,a)\\sim\\mu^{\\pi}$ should be $s \\sim\\mu^{\\pi}$", "limitations": "NA", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 4, "significance": 4, "originality": 3, "strengths_and_weaknesses": "As is evident in the long summary, I did enjoy reading the paper. The problem of offline RL in infinite-horizon MDPs with intractably many states, under weaker conditions like $q^{\\pi}$-realizability and Bellman completeness, is indeed a relevant open problem in the offline RL literature. The paper addresses this problem with an $O(\\varepsilon^{-2})$ sample complexity guarantee and their bound scales linearly with the single-direction coverage parameter, rather than quadratically – which is more common in related works.\n\nThere is no notable weakness. However, I would like to highlight that the algorithm is not fully computationally efficient. It is true that Algorithm 1 can be efficiently implemented with the help of an interior-point method to solve the optimization problem in step 5. While interior-point methods are highly precise, they are not exact. That said, the theoretical guarantees provided in the paper hold under the assumption that there exists an optimization solution which provides an exact solution to step 5. I strongly recommend that the authors add a comment to clarify this, especially in the abstract and other parts of the main text with explicit claims about computational efficiency.", "was_revised": true, "final_justification": "I maintain my positive score of the paper due to the strengths listed above, and a satisfactory discussion with the authors. The paper addresses an important problem in offline RL, with adequate theoretical justifications and very few typos. Furthermore, the authors acknowledged my comments on, and agreed to clarify potentially misleading claims about the computational efficiency of their method.", "rebuttal": "We thank the reviewer for their time and positive review. Please see our response below.\n\n>However, I would like to highlight that the algorithm is not fully computationally efficient. It is true that Algorithm 1 can be efficiently implemented with the help of an interior-point method to solve the optimization problem in step 5. While interior-point methods are highly precise, they are not exact. That said, the theoretical guarantees provided in the paper hold under the assumption that there exists an optimization solution which provides an exact solution to step 5. I strongly recommend that the authors add a comment to clarify this, especially in the abstract and other parts of the main text with explicit claims about computational efficiency.\n\nThank you for raising this point. While we assumed the use of exact solutions, inexact solutions still only incur an additive error proportional to the accuracy of the solution. Specifically, suppose that the optimization problem (6) is solved to within accuracy $\\delta$, so that $J_k$ is within $\\delta$ of the optimal solution and the constraint violation is also at most $\\delta$. The computational complexity of many existing algorithms to obtain such a solution solution scale as $\\log\\delta^{-1}$ [Nesterov and Nemirovskii, 1994].  Then additional error will be incurred in Lemma 6.2 where we will instead have\n$$J_k \\leq J_k^* + \\delta \\le J^{\\pi_k} + \\kappa_{\\mathcal{Q}(B_w), \\Pi} + \\delta,\\quad \\forall k \\in [K].$$ There will also be an error incurred in Lemma 6.3 due to the constraint violations, which can be updated to read\n$$|E_{(s, a) \\sim \\mu} [q_k(s, a) - \\phi(s, a)^{\\top}\\bar{w_k}]| \\leq   2(\\beta + \\delta) \\lVert\\phi^{\\mu}\\rVert_{\\hat{\\Lambda}^{-1}} + \\delta.$$\nHere the factor of $2\\delta$ that is a coefficient of $\\lVert\\phi^{\\mu}\\rVert_{\\hat{\\Lambda}^{-1}}$ is due to the violation of the quadratic constraints and the additive factor is from a violation of the linear constraint. We will add a clarifying statement in the main text accordingly.\n\n>Do the authors assume that the initial state is fixed?\n\nWe do not need to assume that the initial state is fixed. It may be random. Under assumption 3.1, the average reward $J^{\\pi}$ does not depend on the initial state. Therefore, the identity of the initial state, or distribution if it is random, does not change the problem or our results. \n\nThank you for pointing out the typos! We will correct these in the revision. \n\n[Yurii Nestorov and Arkadii Nemirovskii, 'Interior-Point Polynomial Algorithms in Convex Programming', Society for Industrial and Applied Mathematics, 1994]"}, {"review_id": "c9I48UEoiH", "reviewer": "Reviewer_vssp", "summary": "The authors proposed an actor-critic offline reinforcement learning algorithm for average reward MDP, which first achieved O(\\eps^{-2}) sample complexity. As a paper focusing on the theoretical guarantee, the authors provided detailed proof and discussion on the relationship with the previous paper.", "questions": "Please refer to the clarity and Originality Parts for the questions. This paper is technically solid. I would increase the score if the author could confirm with me the question mentioned above.", "limitations": "yes", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Quality: 3\nThe main paper quality is good. The author provided an actor-critic framework to the offline RL problem. Decompose the sub-optimality into actor and critic parts. For the actor parts, the author adopts the Natural policy gradient method and achieves an optimization error convergence with order O(1/\\sqrt(k)). For the critic part, the authors applied Bellman equation regression with pessimism parameters. The proof sketch and details are solid. Moreover, the author discusses the assumption and previous work in depth, which is helpful.\n\nClarity: 2\nDespite the algorithm and proof being solid in this paper, some errors or typos may lead to misunderstanding.\n\n(1)\tIn the section 4.2 policy update, it is better to make it clear that the update follows Mirror Ascent with KL divergence or Natural policy gradient instead of general gradient ascent to make a better understanding\n(2)\tIn the proof of Lemma B.3, the notation \\bar{\\omega}_k and \\omega_k^* are mixed up? Make it hard to read the proof of Lemma B.3\n(3)\tIn the proof of Theorem 5.1, line 610, the optimization error term is missing.\n\nSignificance: 3\nThe authors discussed the convergence rate of the offline RL under the Average MDP setting, which is an important topic in RL theory and closes the gap.\n\nOriginality: 2\nAlthough the discussed problem is important to the community. However, it seems the novelty is somehow limited. The actor-critic framework is followed from [Zanette 2021]. Although I agree that [Zanette 2021] discussed the episodic setting and the induction technique is invalid in the average setting. However, it seems that the idea of proof procedure (Lemma 6.2 and 6.3) is similar to the FOPO algorithms' proof in [Wei et al, 2021]. The only difference is that [Wei et al, 2021] discusses online problems with Optimism, and this paper discusses offline problems with pessimism. \n\nIt would be great to highlight the contribution of the technical part of this paper if the authors could answer the following question.\n\nThe author mentioned that [Gabbianelli et al., 2024] is the only paper that also discusses offline RL under average MDP. However, they only achieve O(\\eps^{-4}). Could the author explain what the new idea or technique is adopted to improve the result to O(\\eps^{-2})?", "was_revised": true, "final_justification": "Reason to borderline accept: close the gap of RL theory in the offline setting, which is important to the community.\nReason not to accept or strong accept: Although the proposed algorithms achieved faster convergece rate, the proof technique is somehow not groundbreaking", "rebuttal": "Thank you very much for your time and detailed review. Please see our responses to your questions below.\n\n### Clarity\nThere are a few typos in the proof. Thank you for pointing these out!\n\nThe $w_k^*$ appearing in the proof of Lemma B.3 is a typo. It should be $\\bar{w}_k$ throughout the proof. We have corrected this.\n\nThe second inequality in line 610 should read $$\\frac{1}{K} \\sum_{k = 1}^{K} J^{\\pi} - \\hat{J_k} + \\kappa_{B_w, B_{\\theta}} \\leq 2B_w \\sqrt{\\frac{\\log A}{K}} + 2\\beta \\lVert\\phi^{\\mu^{\\pi}}\\rVert_{\\hat{\\Lambda}^{-1}} + \\varepsilon_{B_w, B_{\\theta}} + \\kappa_{B_w, B_{\\theta}}.$$\nWe have corrected this as well. \n\nWe will also update section 4.2 to be clear that the policy update follows mirror ascent with KL divergence regularization.\n\n### Originality\n\n> However, it seems that the idea of proof procedure (Lemma 6.2 and 6.3) is similar to the FOPO algorithms' proof in [Wei et al, 2021]. The only difference is that [Wei et al, 2021] discusses online problems with Optimism, and this paper discusses offline problems with pessimism.\n\nAlthough our analysis is partly inspired by [Wei et al., 2021], we would like to point out some notable differences below.\n\n\n1. Unlike [Wei et al, 2021], we do not require the perfect linear MDP assumption. Specifically, we only assume the approximate realizability and restricted closedness properties. Additional work is required for the analysis to handle this level of generality. For instance, in the proof of Lemma 6.2, we cannot assume that $w_k^{\\star}$ parameterizes the true Q-function $q^{\\pi_k}$ exactly. So the function $q_k^{\\star}(s, a) = \\phi(s, a)^{\\top}w_k^{\\star}$ need not be a solution to the Bellman equation. This results in the additional term $\\hat{\\Lambda}^{-1} \\sum_{i = 1}^{N} \\phi(s_i, a_i) \\Delta_{k}(s_i,a_i)$ in equation (17), where $\\Delta_k(s, a) = q_k^{\\star}(s, a) + J_k^{\\star} - T^{\\pi_k}q_k^{\\star}(s, a)$ is the irreducible Bellman error due to realizability holding only approximately. When arguing that $w_k^{\\star}, J_k^{\\star}$ is feasible for the optimization problem (6) with high probability, this term needs to be accounted for. This is why the additional factor of $\\kappa_{\\mathcal{Q}(B_w), \\Pi} \\sqrt{N}$ appears in the definition of the confidence parameter $\\beta$. A similar error term also appears in Lemma 6.3 due to the restricted closedness assumption.\n\n2. Because our algorithm is policy based, our analysis is built on the extended performance difference lemma (Lemma 6.1). This differs from the proof structure in [Wei et al., 2021] since their algorithm takes greedy actions. More specifically, the way we decompose the sub-optimality in step 3 of the proof sketch is quite different. We decompose the sub-optimality into an optimization term and a bias term. Our Lemma 6.3 focuses on controlling the bias in the estimate of the Q-function for each policy $\\pi_k$ encountered during the algorithm's execution. Such a statement does not appear in [Wei et al., 2021] because thier algorithm is designed to approximate the solution to the Bellman optimality equation in each episode, rather than the solution for a fixed policy. They then need to argue that the bias in their estimate of the *optimal* Q function is not too large. Therefore, their regret analysis is based entirely on the Bellman optimality equation and martingale difference concentration rather than a performance difference lemma.\n\n>The author mentioned that [Gabbianelli et al., 2024] is the only paper that also discusses offline RL under average MDP. However, they only achieve O(\\eps^{-4}). Could the author explain what the new idea or technique is adopted to improve the result to O(\\eps^{-2})?\n\nThank you for the question. To explain our new technique, we first briefly summarize the main ideas of [Gabbianelli et al., 2024] using their notation. In their work, they assume a linear MDP structure, realized by $\\Psi \\in R^{d \\times |S|}$, $w \\in R^d$ satisfying $$r(s, a) = \\langle \\phi(s, a), w \\rangle, \\qquad P(s'|s, a) = \\langle \\phi(s, a), \\psi(s') \\rangle,$$ where $\\psi(s')$ is the $s'$ column of $\\Psi$. To adapt to average reward case, they also assume there is some $\\varrho \\in R^d$ with $\\langle \\phi(s, a), \\varrho\\rangle = 1$. Assuming that state action pairs are drawn i.i.d from some distribution $\\mu_{B}$, the population covariance is $\\Lambda = E_{\\mu_B}[\\phi(s, a)\\phi(s, a)^{\\top}]$. Under their linear MDP assumption, they observe the average reward (they call $\\rho^{\\pi}$) can be written as $\\rho^{\\pi} = \\langle \\lambda^{\\pi}, w \\rangle$ where $\\lambda^{\\pi} = E_{(s, a)\\sim \\mu^{\\pi} \\otimes \\pi}[\\phi(s, a)]$. They then formulate the problem as a linear program with Lagrangian $$f(\\beta, \\pi; \\rho, \\theta) = \\rho + \\langle \\beta, \\Lambda[w + \\Psi v_{\\theta, \\pi} - \\theta - \\rho \\varrho]\\rangle.$$\nHere $v_{\\theta, \\pi}(s) = \\sum_{a}\\pi(a|s)\\langle \\phi(s, a), \\theta \\rangle$ and $\\beta = \\Lambda^{-1}\\lambda$ is a reparameterization used so that knowledge of $\\Lambda$ is not necessary to run the algorithm. Their main idea is to solve the saddle point problem $$\\min_{\\rho, \\theta}\\max_{\\beta, \\pi} f(\\beta, \\pi; \\rho, \\theta).$$ Note, importantly, that this is a population level problem. Since they only assume access to i.i.d. samples from $\\mu_{B}$, they solve the problem via stochastic gradient descent-ascent.\n\n The main bottleneck in the analysis of [Gabbianelli et al., 2024] is their algorithm's double-loop structure that, in each outer loop $t$, uses an inner-loop to solve $$\\min_{\\rho, \\theta} f(\\beta_t, \\pi_t; \\rho, \\theta)$$ nearly exactly using $O(\\varepsilon^{-2})$ samples.Then as they need $O(\\varepsilon^{-2})$ outer-loop total iterations, they could only get the $O(\\varepsilon^{-4})$ upper bound. \n \nThe key reason for the sample complexity improvement in our paper is the efficient use of the entire dataset for the critic's optimization problem (6). Namely, the data to construct this problem only needs to be sampled once and is then re-used in each iteration of our algorithm. This avoids the inner-loop that uses additional samples.  The only issue that needs to be dealt with is the statistical correlation between iterates of the algorithm arising from data re-use. This correlation is handled in the analysis using the $\\epsilon$-net covering technique.\n\nWe would also like to point out that the linear program structure of [Gabianelli et al., 2024] crucially relies on the linear MDP structure. Our use of the constrained optimization approach is the key reason we can relax the assumptions to cover restricted closedness and approximate realizability."}, {"review_id": "ggquPpRm1X", "reviewer": "Reviewer_ni8W", "summary": "This paper proposes a pessimistic actor-critic algorithm for offline reinforcement learning (RL) in infinite-horizon average reward Markov Decision Processes (AMDPs), using linear function approximation of the value function. The key technical contribution is a novel, computationally efficient critic step that avoids solving successive sequence of regression problems by directly solving a fixed-point Bellman equation using a linear optimization formulation with convex quadratic constraints. The algorithm is proven to be sample-efficient, with a near-optimal sample complexity of $\\mathcal{\\tilde{O}}(\\epsilon^{-2})$, under a weak notion of data coverage (the feature coverage ratio). This is the first such result in the offline average-reward setting that matches the best known rate and only requires for the MDP induced by all policies to be unichain.", "questions": "N/A", "limitations": "Yes, the authors have adequately addressed the limitations and potential negative societal impact of their work.", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 4, "clarity": 4, "significance": 4, "originality": 4, "strengths_and_weaknesses": "**Strengths:**\n- The paper addresses the problem of offline RL infinite-horizon, average reward setting, an important gap in literature \n- The analysis requires mild assumption compared to prior literature - it requires only unichain (instead of uniformly ergodic) and a relatively weak notion of the feature coverage ratio\n- The algorithm cleverly constructs a pessimistic estimate of the average reward by solving a single fixed-point Bellman equation and address computational efficiency through the reformulation as a linear optimization with convex quadratic constraints\n- Significantly improves upon the sample complexity in comparison to prior offline RL literature and matches the best known in online RL domain\n- Well written paper with a clear presentation of the proof sketch and a through discussion of the assumptions used\n\n**Weaknesses:**\n- A discussion on the effects of scaling state and action space might be nice to include\n- Insight into how the current work may be extended to the general non-linear function approximation setting would make the paper comprehensive\n- While weaker than uniform ergodicity, the unichain assumption may not always hold. As mentioned in the section on future directions, it would be interesting to see how this affects algorithm design and analysis.", "was_revised": true, "final_justification": "Accept because an important problem (offline RL in infinite-horizon, average reward setting) considered, clever algorithm, significant improvement in sample complexity from previous SOTA, well-written\n\nNot Strong Accept because the problem considered is a logical next step in the offline RL line of work and the proof techniques presented are significant but not ground breaking", "rebuttal": "Thank you for your time and detailed review. Please see our responses below.\n\n> A discussion on the effects of scaling state and action space might be nice to include\n\nThe bound in Theorem 5.1 only depends on the size of the action space, and only scales logarithmically with this number. Importantly, the bound does not depend directly on the size of the state space at all, only on the dimension of the feature map $d$. We will be sure to add this discussion in the revision.\n\n> Insight into how the current work may be extended to the general non-linear function approximation setting would make the paper comprehensive\n\nThe main obstacle in generalizing our algorithm in its exact form to more general function approximation is the confidence ellipsoid, $\\lVert \\xi \\rVert_{\\hat{\\Lambda}} \\leq \\beta$ . This is based on martingale concentration techniques from the linear MDP literature (Lemma B.1). These techniques allow us to very precisely quantify the level of uncertainty in the dataset. It is not yet clear how to do this for more general function approximation like neural networks. \n\nHowever a promising avenue may be to adapt techniques from papers such as [Xie et al., 2021] and [Cheng et al., 2022]. Specifically, one can consider removing the pessimism parameter $\\xi$ and considering a Lagrangian relaxation of the critic's problem. Specifically, in episode $k$ we may ask the critic to find a function $q_k\\in \\mathcal{Q}$ minimizing $$J + \\frac{\\lambda}{N} \\sum_{i = 1}^N (q(s_i, a_i) + J - r(s_i, a_i) - E_{a \\sim \\pi_k}[q(s_i', a)])^2,$$ where $\\mathcal{Q}$ is some suitable class for function approximation, $\\lambda$ is a Lagrange multiplier which can be tuned to control the degree of pessimism, and $$\\frac{1}{N} \\sum_{i = 1}^N (q(s_i, a_i) + J - r(s_i, a_i) - E_{a \\sim \\pi_k}[q(s_i', a)])^2$$ is the average square TD error. The main challenge we see here, which is not present in the discounted setting, is the presence of the additional parameter $J$ meant to estimate the average reward of policy $\\pi_k$. Ideally, $J$ should depend on $q$ in such a way such that $J(q_k)$ is a pessimistic estimate of the average reward of policy $\\pi_k$. We leave this interesting problem for future work.\n\n\n>While weaker than uniform ergodicity, the unichain assumption may not always hold. As mentioned in the section on future directions, it would be interesting to see how this affects algorithm design and analysis.\n\nThere are two main difficulties we come across without the unichain assumption. The first is that, in this case, $J^{\\pi}$ not be constant and could depend the initial state. The formulation of the optimization problem (6) may need to change to reflect this. The second is that, without Assumption 3.1, the true Q-functions may be unbounded. The stability of our algorithm relies on the members of the function class $\\mathcal{Q}(B_w)$ being bounded. If the true Q functions are unbounded, but the elements of $\\mathcal{Q}(B_w)$ are, it may be unreasonable to expect the completeness and approximate realizability assumptions to hold. We will add the discussion in the revision."}]

Author rebuttal:

Meta-review: This paper studies an offline actor-critic algorithm for policy optimization on average-reward MDPs with linear (value) function approximation using the pessimism principle. All the reviewers were positive about the contributions of the paper, despite noting some limitations (e.g. reliance on linear approximation, lack of computational efficiency of the procedure). The authors are recommended to include the minor clarifications that they provided to reviewers during the rebuttal/discussion phase in the camera-ready version.
Decision: Accept (poster)