Finite-Time Bounds for Average-Reward Fitted Q-Iteration
Authors: Jongmin Lee
Ernest K. Ryu
Venue: NeurIPS 2025 poster ()
Keywords: reinforcement learning theory
average-reward MDP
fitted Q-iteration
value iteration
sample complexity
anchoring
single-trajectory data
IID data
Primary area: reinforcement_learning
TL;DR: We characterize sample complexities for average-reward offline RL with function approximation for weakly communicating MDPs.

Abstract: Although there is an extensive body of work characterizing the sample complexity of discounted-return offline RL with function approximations, prior work on the average-reward setting has received significantly less attention, and existing approaches rely on restrictive assumptions, such as ergodicity or linearity of the MDP. In this work, we establish the first sample complexity results for average-reward offline RL with function approximation for weakly communicating MDPs, a much milder assumption. To this end, we introduce Anchored Fitted Q-Iteration, which combines the standard Fitted Q-Iteration with an anchor mechanism. We show that the anchor, which can be interpreted as a form of weight decay, is crucial for enabling finite-time analysis in the average-reward setting. We also extend our finite-time analysis to the setup where the dataset is generated from a single-trajectory rather than IID transitions, again leveraging the anchor mechanism.

Finite-Time Bounds for Average-Reward Fitted Q-Iteration
Jongmin Lee
Ernest Ryu UCLA
Seoul National University Department of Mathematical Sciences dlwhd2000@snu. kc.
Department of Mathematics eryu@math, wcla. edu
Abstract
Although there is an extensive body of work characterizing the sample complexity of discounted-retumn offline RL with function approximations, prior work on the everage-reward setting has received significantly less attention, and existing ap- proaches rely on restrictive assumptions, such as ergodicity or linearity In this work, we establish the first sample complexity results for average-reward offline RL with function approximation for weakly communicating MDPs, much milder assumption. To this end, we introduce Anchored Fitted Q-Iteration, which combines the standard Fitted Q-Iteration with an anchor mechanism. We show that the anchor, which can be interpreted for enabling finite-time analysis in the average-reward setting. We also extend our finite-time analysis to the setup where the dataset is generated from single- trajectory rather than IID transitions, again leveraging the anchor mechanism.
MDP.
form of weight decay, is crucial
Introduction
The goal of offline Reinforcement Learning (RL) is to find a near-optimal policy using precollected dataset without any direct interaction with the environment. Characterizing the sample complexity for finding an c-optimal policy using function approximation under assumptions that the offline data has sufficient coverage over whole state-action space has been an active area of theoretical RL research. However, more prior work focuses on the discounted cumulative reward setup, and research on obtaining sample complexity the average reward has been limited due to the absence of the discount factor and the complexity of the Bellman equation. Specifically, all prior works with function approximation rely on restrictive assumptions such as ergodicity or lincarity of the MDP.
Although theoretical RL research often focuses the discounted return setup due to the theoretical convenience offered by the discount factor and the simpler Bellman equation, many practical scenarios are more naturally modeled as agents aim to maximize the average reward. In fact, many practical RL applications do not use discounting at all. These considerations make the sample complexity of average-reward RL relevant, despite the additional technical challenges this setting presents.
Contribution. this work, we introduce the Anchored Fitted Qterratioo and establish the sample complexity on average reward MDPs with general function approximation for weakly communicating MDPs for the first time. consider the cases with IID data and with single-trajectory data. Then, we show that by using the relative normalization mechanism from the classical relative value iteration, we can further improve the sample complexity.
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

Coverage coefficient
Prior works
MDP class
dataset
Ozdaglar et al. [63]
ergodic
IID samples
partial
Gabbianelli al. [30]
unichain" (+ linear)
IID samples
partial
Our work
weakly communicating"
IID samples
full
Our work
weakly communicating"
3-mixing single-trajectory
full
Table 1: Comparison of analyses of offline average-reward MDPs. Our work, which assumes the MDP is weakly communicating, significantly relaxes the structural assumption on the MDP compared to prior work. (Clarification": Ergodic, unichain, and weakly communicating are respectively the standard MDP classes for which the results of [63], [30], and our work apply. However, the precise conditions are slightly more general in each case. See Section 1.2 for detailed definitions.)
weakly communicating
unichain
ergodic
Figure 1: The MDP classes satisfy the inclusion: ergodic C unichain C weakly communicating
1.1 Preliminaries and notations
We briefly review the basic notions of average-reward Markov decision processes (MDPs) and reinforcement learning (RL) and refer the readers to standard references for further details [66, 7, 78].
Aveadd MDP. Let M(X' be the space of probability distributions over X and F(X) be the space of bounded real-valued functions over X. Write (S, A, P.r) to denote an infinite- horizon undiscounted MDP with finite state space S, finite action space A, transition matrix
P: S x >> M(S), bounded reward r: x + [ R. R). Denote n: S M(A) for policy, n² a) lim inf E
a:) 80 8, ag a for the average-reward of policy given an initial state-action pair (s, a), where E,, denotes the expectation over all trajectories (so, ag. $1, ai...., ar) induced by P and
We say т. is an optimal policy if gf (=, max, (s a) for all s S and A, and we say g" - is the optimal average reward. (The optimal policy and optimal average reward exists for finite state-action space [66, Theorem 9.1.8).) We say is an c-optimal policy if g Io S c. Define pa as
(T((s, (s', = Prob((s, + (s',a') P(-ls, a(-1s)),
the transition matrix induced by policy и. Then, (P*Q) a) = = s.0) [Q(s)((ssss a')] for Q E F(S x A). Define the weighted Lp-norm of Q E F(S x A) under state-action distribution as |1 = [E(r,))p (Qss, a)pj// for por221 1.
Coverage coefficient. A coverage coefficient quantifies the shift between the distribution of the offline data and the distribution induced by policies [61, 18]. Loosely speaking, the full coverage assumption, as stated in Table assumes that the offline data sufficiently explores the whole state- action space regardless of policy [4, 92], while partial coverage only requires the offline data to sufficiently explore the state-action pairs that an optimal policy would visit [94, 42). These types of assumptions are fundamentally necessary for the complexity analysis of offline RL [18], and different works use different types of coverage coefficients (cf. [80, 71).. The coverage coefficient we use defined in Section 3.

---

Value Iteration. Given an undiscounted MDP (S, the Bellman optimality operator 7 is
(s) = r(s, + Be a.0))
max Q(s', .a') a'EA
for all s and A. We define the standard Value Iteration (VI)
Q' =T
for 1, 1,,,.... K
where Q" is an initial point.
MDP classes. MDPs are classified according to the structure of the transition matrices. (For definitions on irreducible classes, recurrent classes, transient states, and aperiodicity of transition matrices, refer to [66, Appendix A.2J.) An MDP is ergodic the transition matrices induced by every policy has single recurrent class and is aperiodic. An MDP is unichain if the transition matrices induced by every policy π has a single recurrent class plus a possibly empty set of transient states. An MDP is weakly communicating if there every other state in that set under some policy, plus possibly empty set of states that are transient for all policies. Otherwise, in general, an MDP is multichain. We note that classification of MDPs is crucial in the analyses of average-reward MDPs (96, 97, 88, 50].
of states where every state in the set is accessible from
1.2 Conditions of Prior works
In Table 1, we remarked that the precise conditions the MDPs are slightly general than ergodic, unichain, and weakly communicating, In this section, we state the precise conditions.
Uniform mixing [63]. The uniform mixing condition assumes that there exist positive bmii E N (which does not depend on and p) such that || (P")*--""1 < 1/2 for all t 2 tmaz for any policy and initial distribution p. where n/ is the stationary distribution of p (This condition requires that the stationary distribution n² is unique for all π.) The prior work [63] uses this assumption for its analysis of average-reward MDPs. Ergodic MDPs satisfy the uniform mixing condition [13, 52], but unichain MDPs do not [66, Example 8.2.1].
All-policy Bellman equation and linear MDPs [30]. The all-policy Bellman equation states that for any policy æ, the average reward g" does not depend on (s, a) and there exist Q" S A IR such that
rss, a.) (
(&" (()))))))=((( +9"
for all S and E A. The prior work [30] uses this assumption for its analysis of average-reward MDP. Unichain MDPs satisfy the pol-policy Bellman equation while weakly communicating MDPs, in general, do not [66, Section 8.4]. Also, the uniform mixing condition implies the all-policy Bellman equation [88, Lemma 6].
An MDP is linear if there exist :: S - Rd, vh S Rd. and w E IRd such that
r(s, a) = (ø(s, a), w), P(s' a) (ø(s, a), (ss')).
The linear MDP assumption is often used for theoretical analyses [39, 30J, but it requires knowledge of the mapping 6 and ei and often fails hold in practice [32, 82].
Bellman optimality equation (our work).
Assumption (Bellman optimality equation). The optimal average reward g" does not depend on (s, a) and there exist QT S A + IR such that
r(s, a) + P(.lP) max (T = Q -s.
for all s S and a E A.
A policy т. satisfying the Bellman optimality equation is an optimal policy [88, Section 2]. The all-policy Bellman equation implies the Bellman optimality equation, and the weakly communicating condition of MDPs also implies the Bellman optimality equation [66, Theorem 8.3.2, 8.4.1].
3

---

2 Anchored Fitted Q-Iteration
Consider the offline RL setup with precollected dataset D {st, a, rss s') where r; r((,, a:) and 5f P(- s; 0i). Let F be a nonempty function space to approximate Q-value, We now introduce our novel algorithm, Anchored Fitted Q-Iteration (Anc-F-QI).
Algorithm 1 Anchored Fitted Q-Iteration (D, (
Input: D {&i, 0ig r;, 8 1 So 0, K 2 1, (A:) C (0,1)
for k = 0, ..... K - do
Tfx argmin
Ei=1 (f(s;,
- - m fa((),,
fa+1 = (1 - f4 + Ak end for
D> With fo = 0, this is weight decay
Ta 8) argmax (x(8,a)
Output म. fK
In Section 4, we present our sample complexity results for Anc-F-QI. Roughly speaking, Theorem 1 establishes (11/5)) /e") sample complexity with IID data and Theorem establishes ((1/e22) sample complexity with 3-mixing single-trajectory data. In Section 5, to further improve the sample complexity with the Relative Anchored Fitted-Q Iteration, establishing ((1/e²) and (11/e²) sample complexities for IID and single-trajectory data, respectively.
2.1 The anchor mechanism and weight decay
Our method Ane-F-QI stated Algorithm I consists of two main components. The first component the first line of the for-loop, the classical Fitted Q- Iteration [25, 61] step without discount factor. Its goal is to find the function 7 f 2 fk, where is the Bellman operator. However, unlike Fitted Q-Iteration in the discounted cumulative reward case, Í // RJ Th is not enough to establish a finite sample complexity in the average-reward setup. In the tabular case where the Fitted Q-Iteration reduces to Value Iteration (VI), it is known that VI might not converge. Specifically, there exists an average-reward MDP such that the policy error of VI does not converge to zero [22, Example 4). Even if an aperiodicity condition is assumed, VI guarantees only asymptotic convergence without any known explicit convergence rate the average-reward setup [66, Theorem 9.4.5].
Recently, Anchored Value Iteration (Anc-VI was proposed to obtain finite-tine time bounds of policy error for average- reward MDPs [14, 50, 48). Particularly, the Anchored Q- D-Value Iteration is
Q = (1=) xx) +
TQ
for h: = 1, .... 1,,
(Anc-QI)
where A parameter is to be chosen. Compared the standard VI, Ane- Mic-QI obtains the next iterate as a convex combination between the output of and the starting point Q". We call the (1 - Ao)Qo term the anchor term since it serves to pull the iterates back toward the starting point Qo- With this Anc- VI, [50] establish non-asympo convergence in the average-reward reward setup. Specifically, Ane-VI VI exhibits the O(1/k -rate in terms of policy error [50][Theorem] 2 and Corollary 2] without any restrictions on the MDP.
This anchoring mechanism, classically also known the Halpern iteration [33]. has been widely studied in minimax optimization and fixed-point problems [70, 55, 65, 20, 93]. In the context of reinforcement learning, [49, 50) applied the anchoring mechanism to VIs for cumulative-retura and average-reward MDPs under the tabular setting, and [14, 48] applied the anchoring mechanism to Value Iteration for cumulative-retum and average reward MDPs under the generative model setting.
In this work, we combine Fitted Q-tteration with anchoring, as shown in the second line of the for-loop of Algorithm 1, and establish finite-time bounds on the sample complexity.
2.2 Assumptions on the function space F
Assumption 2 (existence of argmin). In Anc-F-QI, the argmin defining T fx exist for k: = O,..., K 1.
This assumption is needed for the regression step of Algorithm I to be well defined.

---

Assumption 3 (star-shaped function space). If F,nf E F for all 1j E [0, 1].
This assumption implies that the anchor step of Anc-F-QI to be well defined. Star-shaped function
space is a classical notion that relaxes convexity [31, 34, 51], and if F corresponds parametrized neural network with a linear layer as the output layer, F is star-shaped.
Definition 1 (Inherent Bellman error). Define 6B (B(F F) max minger II ffll as the inherent Bellman error with respect to the norm
The inherent Bellman error quantifies the error due to the function spaces F F in approximating the output of the Bellman operator [61, 3, 18]. Note that the function spaces F, F' are bounded (in the || norrm, then 5 is also bounded.
Assumption 4 (Bellman completeness).
(F) O, where cp the is inherent Bellman error.
Bellman completeness states that if F, then Tf E Le.. operator. Although the Bellman completeness assumption is seemingly strong, is often considered in sample complexity analyses in the offline RL literature [18, 26J. In fact, the Bellman completeness condition is fundamental in the sense that the prior work [28] showed that a polynomial sample complexity cannot be established without Bellman completeness assumption.
are closed under the Bellman
3 Approximate Anchored Q- Iteration
In this section, conduct an Lp bound analysis that will later be used establish the main sample complexity results of Sections 4 and 5. Define the Approximate Anchored Q- Q-Value Iteration as
Q (1 A Q + +x(TT + +E)
(Apx-Anc-QU)
for 1: 1,2, ...., K, where T is the Bellman operator, Qo E RR is starting point, and 6 represents the evaluation error of TQK-1, We choose d
k k+2 for k l,..., K, motivated by [70, 20].
We now establish a convergence analysis of Apx- QI based on Lp bounds of cg. Similar to the prior work [59, 60, 26), assume the following coverage coefficient for our analysis. Assumption (uniform stochastic transition). For given distribution μ on A.
D (-1 81
CN def sup
< <C.
(x(+)
s,0,5
Assumption (uniform future state distribution). For given distributions μ and p on S x A.
Tmmpae prpppp....p .p. F1
def
Cp.p
sup
00;
p(-)
where Ti, .2.... represents an arbitrary sequence of policies.
The coverage coefficients measure the mismatch between the distribution of offline data and the distribution induced by the transition matrices and initial distributions. We note that Assumption implies Assumption 6 with Cu.p S Cp [61, Section 5].
Proposition 1. Let p [1, co), and let and p be distributions on S x A. Under Assumption I and 5 (Bellman optimality equation, uniform stochastic transition), the policy error of Apx-Anc-QU with A k-2 satisfies
&
11g 9TT 100 S SCL/P K+2 K+21Q0 QQIIn.. + C²/F" C2/22K 2K
8
max ||ex|Ip.a. ISkSK
Similarly, under Assumption I and 6 (Bellman optimality equation, uniform future state distribution), the policy error of Apx-Anc- Q1 with A
l.
satisfies
k42
C2/p u.p K K+ -1Q 1l. . + C1/pp 2K
11g "Il.n S
max ||ex|pp.a-
P.P 3
1skSk
To clarify, the g-, Q- and e-terms in Proposition 1 are functions of (s, a) and the norms || llppp and || Il taking expectations with respect to the distributions p and μ.
The bounds of Proposition serve as the technical crux of our sample complexity results later presented in Theorems 1, 2, 3. and 4. In the bound, the first term decreases with order O(1/ K) but the second error term increases with order @KK). Therefore, our subsequent arguments will ensure ||el||p. () by using sufficient offline samples.
5

---

Sample complexity of Anchored Fitted Q-Iteration
We now present sample complexity analyses of Anc-F-QI with IID and single-trajectory data.
4.1 Range of function space F
Before analyzing the complexity of those, we explain our issue on range of function space in average-reward setup and our choice of function space.
When considering Fitted Q- Iteration in the discounted reward setup, the functions often assumed to be bounded by ||2 [61, 18], where Q is optimal state-action function with discount factor 7, since Il < || implies |T I |1 In the average-reward setup (without discounting), this property does not hold, and the Fitted Q-Iteration is expected to produce an unbounded sequence functions. To address this issue, we allow the range of the function space to increase with each iteration.
Assumption 7 (increasing function range). Let Fo (0} and Fs c U I-RR, kRt E B(S A)} and J& E Fx in Anc-F-QI for all k.
Roughly speaking.
f ~ |T
maxx fk-1 aEA
2 R 1ff--f 2 SRR+ ffoll
so we increase the function bound as k.R.
4.2 IID dataset
In this subsection, we study sample complexity with IID dataset.
Assumption 8 (IID dataset). There is distribution ys such that the dataset is {8t, as Ti $ generated IID with (s;, a,) ~ it and s P(- s;, 0;) for 1....,
Since we consider possibly infinite function space, as measurement of the capacity function space, use covering number [21, 83].
Definition 2. An e-cover of set S with respect to metric d is set (0:) C such that for all E S, there is an i {1....,N] NY such that d(8, 8¹) I e. The covering number (ee d) is the cardinality of the smallest e-cover. By convention, define N++oo; S, = 1.
We now present lemma which bounds approximation error of Anc-F-QI QI for IID dataset.
Lemma 1. Assume Assumptions 2, 3, 7, and 8 (Bellman optimality equation, existence of argmin,
star-shaped function space, increasing function range, IID dataset). Let μ be the distribution
generating the dataset. Let and 6 > With probability 1 8, (fNy T'kkk K of Anc-F-QI
with As- E42 satisfies
60(k 2) (n No, Ne, +3c 13c Fs+1),
11T -ff S
n
where
No.c N 105(2k-1)7 Fe: Fer I1:l)bo), for k = 0, 0,1,...,
We defer the proofs to Appendix D, but quickly note that the proof is based on Bernstein inequality and is motivated by [21, 18).
Lemma I tells that the square of approximation enror of the Bellman operator decreases sublinearly with respect to number of sample. Combining Theorem and Lemma 1, we obtain following sample complexity result of Anc-F-QI with IID dataset.
Theorem 1. Assume Assumptions 1, 2, 3, 5, 7, and 8 (Bellman optimality equation, existence of argmin, star-shaped function space, uniform stochastic transition, increasing function range, IID dataset). Let μ be the distribution generating the dataset. Let > 0 and 8 > O. With probability

---

1 5, the policy error of Anc-F-QI with d
t and K
satisfies
Et2
11g 9=* olo S E +3KC
max VEB(FR. Fk+1) with sample complexity k=
Re 1011lQ""111,,, log 1og(N2/0))
112,
n Ō=Ō
e
where Ô ignores all logarithmic factors except the logarithmic dependence on the covering number Ne defined
N. max NK. k= K
NK.c = N LIPRRCAII IB,.. :FR, for lork- =o...,....
Alternatively assume Assumptions 1, 2, 3, 6, 7, and (Bellman optimality equation, existence of argmin, star-shaped function spuce, uniform future state distribution, increasing function range, IID dataset). Let μ be the distribution generating the dataset and p be an arbitrary distribution on S A. Let 0 and 5 O. With probability 6, the policy error of Anc-F-QI with X5=
and &
k42
K [18C Q1Q [2, satisfies 11g g** 1|z.p
3K
(en(
k=0....
with sample complexity
R2C p. p.p 10a 11 log(N?
n= n=Ō
where Ô ignores all logarithmic factors except the logarithmic dependence on the covering number Ng defined as
Ne
NR.e: k=1....K
NR.e = - 1.p FR. 11:loo)))) for k 1,...,, K
In the Appendix D, we show the full sample complexity with the logarithmic factors.
Under the additional assumption Bellman completeness (ep 0), this theorem guarantee that Ane- F-QI produces e-optimal policy with ((1/e)) sample complexity. To the best of our knowledge, this is the first sample complexity result only assuming the Bellman optimality equation or a weakly communicating MDP. In Section 5, we improve this sample complexity to O(1/c) using the relative normalization mechanism.
4.3 Sinelo-traeectory dataset
In this subsection, we study sample complexity with single-trajectory dataset. Assumption 9 (single-trafe trajel--tajettrry dataset). For given behavior policy nu and initial distribution S, datasel is D = {8i, as, ri) where 81 ~ 0s ~ TT(- [-((-1 (1), 8641 ~ P(- 8i, az).
The main technical challenge with single-traj trajectory data is handling the dependency between samples. Following [4, 3], we introduce the following 3-mixing condition ensuring that samples are sufficiently representative and rapidly mixing.
Definition 3 (8-mixing). Let {Zr be a stochastic process. Denote by Z the collection of (Zi...., Ze) where we allowed 3C. Let (Zz*)) denote the o-algebra generated by 2 (i S j). The m-th B-mixing coefficient of {2,) is defined as
8m sup t21
sup BEa m000)
P(B Z -(BIZ
{Z) is said to be B-mixing if 3. - 0 as co. In particular, we say that a B-mixing process mixes at exponent rate with parameters 3, b, if Bm S BBerp((-baa holds for all 2
Roughly speaking, the 8-mixing condition ensures that future samples depend weakly on the past samples. We assume that our angle-trajectory, is 8-mixing and the distribution is in steady state, following [4, 3].
Assumption (3-mixing single-trajectory). For single-trajectory dataset (8i, ai, I's T assume that is strictly stationary with s; and B-mixing exponent rate with parameters 3, b, K > O.
7

---

Again, following [4. 3]. as measurement of the capacity of function space, we use pseudo dimension which has been widely studied for complexity analyses with various function classes [2. 83).
Definition 4 (pseudo dimension). For a given function class F of binary-valued functions, we say the set x. = (r1,..., In is shattered by F if cardinality of (Z1))...... ((x))) : FF is 2". The VC-dimension V5 of F is defined as the largest integer n. such that there exist the set xi shattered by F. For given class F of real-valued functions, the pseudo-dimensioe Vx of is defined as the VC-dimension of the set of indicator function of the subgraphs of functions in F.
We now present lemma which bounds approximation error of of Anc-F-QI for single-trajectory dataset.
Lemma 2. Assume Assumptions 1, 2, 3, 7, 9, and 10 (Bellman optimality equation, existence of argmin, star-shaped function space, increasing function range, single-trajectory dataset, 3-mixing single-trajectoryy) Let p. be the distribution generating the dataset defined as p(s, a) v(s)so((oe mo(a) s). Let é > and 8 O. With probability
Us, Tsk K-1 Anc-F-QQ with X = R#2 satisfies
(max(x 11)1/=
1T - ffa1 S
+ +en (Fn,
where Co.k = (VJe+1 + +V(5x) ) log (ogg//+oogee(KK]) +oo (oogg(aaa(...........0 (c1,k: 3)), c1,k = 16e (V ()((F))mmr + (2(2))) Vie+i mmar C2.k 312(2++3) V(Fe)maz V/. log(3) Al).
We defer the proofs to Appendix D, but we quickly note that the proof strategy closely follow [4, 3] and relies on the Hoeffding inequality under a mixing condition.
Rougbly speaking, Lemma 2 tells that the square of approximation error of the Bellman operator decreases at a / rate with respect to number of sample. Combining Theorem and Lemma 2, obtain following sample complexity result of Anc-F-QI with single-trajectory dataset.
Theorem 2. Assume Assumptions 1, 2, 3, 5, 7, 9, and 10 (Bellman optimality equation, existence of argmin, star-shaped function space, uniform stochastic transition, increasing function range, single-trajectory dataset, 3-mixing single-trun tigle-trajectory), Let μ be the distribution generating the dataset defined as u(s,a) = v(s)mp(a) 8). Let e > and > 0. With 8 probubility, the policy error of Anc-F-QI with d E+z and K [9c 110= 11@==l2,, / satisfies llg g" 1l S
k
++ KCP
max
with sample complexity
n 010
where Ô only shows the dependence on Alternatively, Assume Assumptions 1, 2, 3, 6, 7, 9, and 10 (Bellman optimality equation, existence of argmin, star-shaped function space. uniform future state distribution, increasing function range, single-trajectory dataset, B-mixing single- trajectory). Let μ be the distribution generating the dataset defined as uus, = v(s)TT(a s) and p be an arbitrary distribution on S A. Let >> and 5 0. With 8 proba- satisfies Fxt1) with sample complexity
bility, the policy error of Anc-F-QI with d = K+2 and K =
I|g - grt 112,p S CKK///
max & O...,K
n = ô (1
where Ô only shows the dependence on e.
In the Appendix D, we show the full sample complexity with all of the factors.
To the best of our knowledge, this is the first sample complexity result with single-trajectory data in the average-reward setup. In Section 5, we improve this sample complexity to ((--8) using the relative normalization mechanism
8

---

5 Relative Anchored Fitted Q-Iteration
In this section, we propose Relative Anchored Fitted Q- Q-lttration (R-Anc-F-QQ F-Q) and improve the sample complexity. We are motivated by the classical relative value iteration [90]. In the tabular case, it is known that standard VI diverges in the average-reware setup [66, Theorem 9.4.1], I], and relative value iteration normalizes the divergent vectors [66, Section 8.5.5]. In the case of (Anchored) Fitted Q-Iteration, this normalization allows the /x functions to be bounded and removes the inefficiency associated with the increasing function classes described in Section 4.1.
Algorithm 2 Relative Anchored Fitted Q-Iteration K, (1:)
Input: D {s,, 0g ra s 1= fo 0, 12 1, (A C (0,1) for k = 0, 1,.... K do
Tfx argminjEs Li=1 (f(s; a:) ri m fx(86 a))²
f (1 fo + Ak+1 (T fax f/ 1)
end for
8) [a
argmax fx(ssa)
Output ,. JK
The only difference with Anchored Fitted Q-Iteration is the subtraction of max 2 +min fa in the second line of the for-loop. By direct calculation, can check that || max f-mim 1 2o and subtracting a uniform constant does not effect on greedy policy due the that the Bellman operator satisfies T(cl + z) = cl + T(x). Thus, we can still apply Proposition I to Relative Anchored Fitted I-ttrtntion
| ol
2
Assumption 11 (normalized function space).
EF,, max /+min ( F.
2
This assumption ensures that the normalization operation is well Idefined.
Assumption 12 (range of function space). F (f 8 x A + [-2 11 12 BS x A)}, where QT is solution of Bellman optimality equation.
Now, unlike increasing function range used for the non-relative Anchored Fitted Q-Iteration, now have a function space bounded by Q= This difference leads to improved efficiency as the following sample complexity results show.
Theorem 3. Assume Assumptions 1, 3. 11, and 12 (Bellman optimality equation, existence of argmin, furcetionduunntionn space, uniform stochastic transition, normalized function functtio space, range of function space, III) dataset). Let p be the distribution generating the dataset. Let and > O. With probability 1 1 5, the policy error of R-Anc-F Sane---Q.. with >₁- = k
k-+2 and = [18C]] (18c)//1l00 [1Q ||2,
satisfies 1|g g* 1l sc+ (33Kch/2 122 VCB(F,F) with sample complexity
n Ō (R (R+ 11 1100) ) 11Q 113 C, (og((N//))
el
where Ô ignores all fucttos except the logarithmic dependence on the covering number N, defined as
W 10*C 1Q 11 :1
24
Alternatively, assume Assumptions 1, 2, 3, 6, 8, 11, and 12 (Bellman optimality equation, existence of argmin, star-shaped function space, uniform future state distribution, normalized function space, range of function space, IID dataset) Let μ be the distribution generating the dataset and p be an arbitrary distribution on S x A. Let > 0 and ê > 0. With probability 1 1- 8, the policy error of R-Anc-F-4 F-II with d 1サ2 and K [18C) 1/2 1| [l2, satisfies I|g - g 112,p S
++ 3/2 /en(F,F) F) with sample complexity
n n= ō ( (R+ 1 ) 11Q 12 O3 1og(N220))
el

---

where Ô ignores all logarithuic factors except the logarithmic dependence on the covering number N₂ defined
N₂ = - (1 10 (R+ 11 1112=-111 1 :F,111ll
Theorem 4. Assume Assumptions I, 2, 3, 5, 9, 10, 11, and 12 (Bellman optimality equation, existence of argmin, star-shaped function space, uniform stochastic transition, normalized function funciioo space, range of function space, single-trajectory dataset, 3-mixing single-trujectory) Let be the distribution generating the dataset defined as u(s,a) v(s)Tb(a
[s). Let e > 0 and 0. With k and K = [9C, 1 probability 1 - 6, the policy error of Anc-F-QI with A = k+2
satisfies I1g g= llac S sc+KCy KCP Ven(F. (F) with sample complexity
n= - (1/E))
where O only shows the dependence Alternatively, assume Assumptions 1, 2, 3. 6, 9, 10. 11, and 12 (Bellman optimality equation, existence of argmin, star-shaped function space, uniform future state distribution, normalized function space, range of function space, single-trajectory dataset, 3-mixing single-traeectrry. Let μs be the distribution generating the dataset defined as p(s. = v<s)To(aa))) |) and be an arbitrary distribution on S x A. Let 0 and 5 > 0. With probability - 6, the policy error of Anc-F-QI with A = k42 and K = [9C |1
satisfies Ilg g* 1|,,p S + KC V (FB(F,FFF with sample complexity
Ô (1/e),
where O only shows the dependence on c.
Indeed, with the relative normalization mechanism, we improve the sample complexities from O(1/c)) O(1/c)) and ((1/c²2) O(1/e) for IID and single-trajectory data cases, respectively,
Conclusion
In this work, introduced Anchored Fitted Q-Iteration (Ane-F-QI) and established sample complexity results for the average-reward offline RL with general function approximation under the assumption of weakly communicating MDPs. Our approach combines the classical Fitted Olttrration with an anchoring mechanism, and the anchor mechanism is the crucial component that enables the finite-time analysis. Roughly speaking, we establish a Õ(1 sample complexity with IID data and (() sample complexity with single-trajectory data. Then, using the relative normalization technique, we improve the sample complexity to (11/c²) and ((1/**) for IID and single-trajectory data, respectively.
One limitation of this work the reliance on full coverage coefficients as described Assumptions and 6. Some prior work, such [64] and [30], utilizes weaker assumption that we refer as partial coverage coefficients, albeit with much stronger structural assumptions on the MDP. Extending our analysis relax the full coverage coefficient would be a worthwhile direction of future work. Another possible direction of future work is to utilize variance reduction techniques in the style of [84, 75, 48] to further improve the sample complexity.
Acknowledgments and Disclosure of Funding
This work is supported by the National Research Foundation of Korea (NRF) grant funded by the Korean government 200005-2024000422003)
10

---

References
[1] R. Agarwal, D. Schuurmans, and M. Norouzi. An optimistic perspective on offline reinforcement learning, International Conference Machine Learning, 2020.
[2] M. Anthony and P. L.. Bartlett. Neural network learning: Theoretical feeeoeeiiallounnatiinn Cambridge University Press, 2009.
[3] A. Antos, C. Szepesvári, and R. Munos. Fitted Q-iteration continuous action-space MDPs. Neural Information Processing Systems, 2007.
[4] A. Antos, C. Szepesvári, and R. Munos. Learning near-optimal policies with bellman-residual minimization based fitted policy iteration and single sample path. Machine Learning, 2008,
[5] Q. Bai, W. U. Mondal, and V. Aggarwal. Regret analysis of policy gradient algorithm for infinite horizon average reward markov decision processes. International Conference on Artificial Intelligence, 2024.
[6] R. Bellman. A Markovian decision process. Journal of Mathematics and Mechanics, 6(5):699- 684, 1957.
[7] D. P. Bertsekas. Dynamic Programming and Optimal Control, volume II. Athena Scientific, 4th edition, 2012.
[8] D. Bertsekas and J. Tsitsiklis. Neuro-Dynamic Programming. Athena Scientific, 1996.
[9] D. Blackwell. Discrete dynamic programming. The Annals of Mathematical Statistics, 33:719-
726, 1962.
[10] A. Blumer, A. Ehrenfeucht, D. Haussler, and M. K. Warmuth. Learnability and the Vapnik- Chervonenkis dimension. Journal of the ACM, 36(4):929-965, 1989.
[11] V. Boone and 7. Zhang. Achieving tractable minimax optimal regret average reward MDPs. Neural Information Processing Systems, 2024.
[12] H. Bourel, A. Jonsson, O.-A. Maillard, and M. S. Talebi. Exploration in reward machines with low regret. International Conference on Artificial Intelligence and Statistics, 2023.
[13] R. Bradley. Basic properties of strong mixing conditions. survey and some open questions. Probability Surveys, 2: 107--44 2005.
[14] M. Bravo and J. P. Contreras. Stochastic Halper iteration in normed spaces and applications to reinforcement learning. arXiv preprint arXiv:2403. /2338, 2024.
[15] A. N. Burnetas and M. N. Katehakis. Optimal adaptive policies for Markov decision processes. Mathematics of Operations Research, 22(1):222-255. 1997.
[16] M. Carrasco and X. Chen. Mixing and moment properties of various garch and stochastic volatility models. Econometric Theory, 18(1):17-39, 2002.
[17] Chang, M. Uehara, D. Sreenivas, R. Kidambi, and W. Sun. Mitigating covariate shift in imitation learning via offline data with partial coverage. Neural Information Processing Systems, 2021.
[18] Chen and Jiang. Information-theoretic considerations in batch reinforcement learning. International Conference on Machine Learning, 2019.
[19] M. Chen, A. Beutel, P. Covington, Jain, F. Belletti, and E. H. Chi. Top-k off-policy correction for reinforce recommender system. Proceedings of the Twelfth ACM International Conference on Web Search and Data Mining, pages 456-464, 2019.
[20] J. P. Contreras and R. Cominetti. Optimal error bounds for non-expansive fixed-point iterations in normed spaces. Mathematical Programming, 199(1-2):343-77, 2022.
[21] Cucker and S. Smale. On the mathematical foundations of learning. Bulletin of the American mathematical society, 39(1):1-49, 2002.

---

[22] E. Della Vecchia, S. Di Marco, and A. Jean-Marie. Illustrated review of convergence conditions of the value iteration algorithm and the rolling horizon procedure for average-cost MDPs. Annals of Operations Research, 199:193-214, 2012.
[23] V. Dewanto, G. Dunn, A. Eshragh, M. Gallagher, and F. Roosta. Average-reward model-free reinforcement learning: systematic review and literature mapping. urXiv:2010.08920, 2020.
[24] Y. Duan, Z. Jia, and M. Wang. Minimax-optimal off-policy evaluation with linear function approximation. International Conference on Machine Learning, 2020.
[25] D. Ernst, P. Geurts, and L. Wehenkel. Tree-based batch mode reinforcement learning. Journal of Machine Learning Research, 2005.
[26] Fan, Z. Wang, Y. Xie, and Z. Yang. A theoretical analysis of deep Q-learning Learning for dynamics and control, 2020.
[27] A. Federgruen, P. Schweitzer, and H. C. Tijms. Contraction mappings underlying undiscounted Markov decision problems. Journal of Mathematical Analysis and Applications, 65(3):111-730, 1978.
[28] D. J. Foster, A. Krishnamurthy, D. Simchi-Levi, and Y. Xu. Offline reinforcement learning: Fundamental barriers for value function approximation. arXiv preprint arXiv:2111.10919, 2021.
[29] R. Fruit, M. Pirotta, A. Lazaric, and E. Brunskill. Regret minimization in MDPs with options without prior knowledge. Neural Information Processing Systems, 2017.
[30] G. Gabbianelli, G. Neu, M. Papini, and N. M. Okolo. Offline primal-dual reinforcement learning for linear MDPs. International Conference on Artificial Intelligence and Statistics, 2024.
[31] J. Gardner. Geometric Tomography. Cambridge University Press, 1995.
[32] A. Ghosh, R. Chowdhury, and A. Gopalan. Misspecified linear bandits. The Association for the Advancement of Artificial Intelligence, 2017.
[33] B. Halpern. Fixed points of nonexpanding maps. Bulletin of the American Mathematical Society, 73(6):957-961, 1967.
[34] G. Hansen, I. Herburt, H. Martini, and M. Moszyúska. Starshaped sets. Aequationes Mathemat- icae, 14010-11 2020.
[35] D. Haussler. Sphere packing numbers for subsets the Boolean n-cube with bounded Vapnik- Chervonenkis dimension. Journal of Combinatorial Theory, Series A, 69(2):217-232, 1995.
[36] R. A. Howard. Dynamic Programming and Markov Processes. John Wiley and Sons, 1960.
[37] G. Hübner. Improved procedures for eliminating suboptimal actions in markov programming by the use of contraction properties. Transactions of the Seventh Prague Conference on Information Theory, Statistical Decision Functions, Random Processes. 1977.
[38] T. Jakseh, R. Ortner, and P. Auer. Near-optimal regret bounds for reinforcement learning. Journal of Machine Learning Research, (1651):1533-166 2010.
[39] C. Jin, Z. Yang, Z. Wang, and M. I. Jordan. Provably efficient reinforcement learning with linear function approximation. Conference on learning theory, 2020.
[40] Y. Jin, R. Gummadi, Z. Zhou, and J. Blanchet. Feasible Q-learnigg for average reward rein- forcement learning. International Conference on Artificial Intelligence and Statistics, 2024.
[41] Y. Jin and A. Sidford. Towards tight bounds on the sample complexity of average-reward MDPs. International Conference on Machine Learning, 2021.
[42] Y. Jin, Z. Yang, and Z. Wang, Is pessimism provably efficient for offline RL? International Conference on Machine Learning, 2021.
[43] M. R. Kosorok and E. B. Laber. Precision medicine. Annual review of statistics and its application, 6(1):263-288) 2019.
12

---

[44] A. Kumar, J. Fu, M. Soh, G. Tucker, and S. Levine. Stabilizing off off-policy Q-learning via bootstrapping error reduction. Neural Information Processing Systems, 2019.
[45] A. Kumar, A. Zhou, G. Tucker, and Levine. Conservative Q-learning for offline reinforcement learning. Neural Information Processing Systems, 2020.
[46] N. Kumar, Y. Murthy, I. Shufaro, K. Y. Levy, R. Srikant, and S. Mannor. On the global convergence of policy gradient in average reward Markov decision processes. International Conference Learning Representations, 2025. 2025..
[47] N. Kumar, K. Wang, K. Y. Levy, and S. Mannor. Efficient value iteration for s-rectangular robust Markov decision processes. International Conference on Machine Learning, 2024.
[48] J. Lee, M. Bravo, and R. Cominetti. Near-optimal sample complexity for MDPs via anchoring. Interantional Conference on Machine Learning. 2025.
[49] Lee and Ryu. Accelerating value iteration with anchoring. Neural Information Processing Systems, 2023.
[50] J. Lee and E. Ryu. Optimal non-asymptotic rates of value iteration for average-reward MDPs. International Conference on Learning Representations, 2025.
[51] O. Leong, E. O'Reilly, and Y. S. Soh. The star geometry of critic-based regularizer learning. Neural Information Processing Systems, 2024.
[52] D. A. Levin and Y. Peres, Markov chains and mixing limes. American Mathematical Soc., 2017.
[53] S. Levine, A. Kumar, G. Tucker, and Fu. Offline reinforcement learning: Tutorial, review, and perspectives on open problems. arXiv preprint arXiv:2005.01643 2020.
[54] T. Li, F. Wu, and G. Lan. Stochastic first-order methods for average-reward Markov decision processes. Mathematics of Operations Research, 2024.
[55] Lieder. On the convergence rate of the Halpern-iteration. Optimization Letters, 15(2):405-418, 2021.
[56] Y. Liu, A. Swaminathan, A. Agarwal, and E. Brunskill. Provably good batch off-policy reinforcement learning without great exploration. Neural Information Processing Systems, 2020.
[57] S. Mahadevan. Average reward reinforcement learning: Foundations, algorithms, and empirical results. Machine Learning, 22(1):15--195, 1996.
[58] V. Mnih, K. Kavukcuoglu, D. Silver, A. A. Rusu, and et al. Human-level control through deep reinforcement learning. Nature, 518(7540):529-533 2015.
[59] R. Munos. Error bounds for approximate value iteration. Association for the Advancement of Artificial Intelligence, 2005.
[60] R. Munos. Performance bounds in -norm for approximate value iteration. SIAM journal on control and optimization, 46(2):541-566) 2007.
[61] R. Munos and C. Szepesvári. Finite-time bounds for fitted value iteration. Journal of Machine Learning Research, 9(5), 2008.
[62] Y. Murthy and R. Srikant. On the convergence of natural policy gradient and mirror descent- like policy methods for average-reward MDPs. IEEE Conference on Decision and Control, pages 1979-1984, 2023.
[63] A. Ozdaglar, S. Pattathil, J. Zhang, and K. Zhang. Offline reinforcement learning via linear- programming with error-bound induced constraints. arXiv preprint arXiv:22/2. /3861, 2024.
[64] A. E. Ozdaglar, S. Pattathil, J. Zhang, and K. Zhang. Revisiting the linaa-programmiig framework for offline RL. with general function approximation. International Conference on Machine Learning, 2023.
13

---

[65] J. Park and E. K. Ryu. Exact optimal accelerated complexity for fixed fixed-point iterations. Interna- tional Conference on Machine Learning, 2022.
[66] M. L. Puterman. Markov Decision Processes: Discrete Stochastic Dynamic Programming. John Wiley and Sons, 2nd edition, 2014.
[67] P. Rashidinejad, B. Zhu, C. Ma, J. Jiao, and S. Russell. Bridging offline reinforcement learning and imitation learning: A tale of pessimism. Neural Information Processing Systems, 2021.
[68] A. Rosenberg and Y. Mansour. Oracle-efficient regret minimization in factored MDPs with unknown structure. Neural Information Processing Systems, 2021.
[69] S. Ross and J. A. Bagnell. Agnostic system identification for model-based reinforcement learning. International Conference on Machine Learning, 2012.
[70] Sabach and S. Shtern. A first order method for solving convex bilevel optimization problems. SIAM Journal on Optimization, 27(2):640-660, 2017.
[71] B. Scherrer. Approximate policy iteration schemes: A comparison. International Conference on Machine Learning. 2014.
[72] Schweitzer and A. Federgruen. The asymptotic behavior of undiscounted value iteration in Markov decision problems. Mathematics of Operations Research, 2(4):360-381, 1977.
[73] P. J. Schweitzer and A. Federgruen. Geometric convergence of value-iteration in multichain Markov decision problems. Advances in Applied Probability, 11(1):188-211 1979.
[74] E. Seneta. Non-Negative Matrices and Markov Chains. Springer Science & Business Media, 3th edition, 2006.
[75] A. Sidford, M. Wang. X. Wu, and Y. Ye. Variance reduced value iteration and faster algorithms for solving Markov decision processes. Naval Research Logistics, 70(5):423-442, 2023.
[76] N. Y. Siegel, J. T. Springenherg, F. Berkenkamp, A. Abdolmaleki, M. Neunert, T. Lampe, R. Hafner, N. Heess, and M. Riedmiller. Keep doing what worked: Behavioral modelling priors for offline reinforcement learning. International Conference on Representation Learning, 2020.
[77] R. S. Sutton. Learning to predict by the methods of temporal differences. Machine Learning, 3:9-44, 1988.
[78] R. S. Sutton and A. G. Barto. Reinforcement Learning: An introduction. MIT press, 2nd edition, 2018.
[79] C. Szepesvári. Algorithms for Reinforcement Learning. Morgan Claypool Publishers, 2010.
[80] M. Uehara and W. Sun. Pessimistic model- offline reinforcement learning under partial coverage. International Conference on Representation Learning. 2022.
[81] Van Der Wal. Stochastic dynamic programming: successive approximations and nearly optimal strategies for Markov decision processes and Markov games. 1981.
[82] D. Vial, A. Parulekar, S. Shakkottai, and R. Srikant. Improved algorithms for misspecified linear markov decision processes. International Conference on Artificial Intelligence and Statistics, 2022.
[83] M. J. Wainwright. High-dimensional statistics: A non-asymptotic viewpoint. Cambridge university press, 2019.
[84] M. J. Wainwright. Variance-reduced Q-learning is minimax optimal. arXiv preprint arXiv: Ttt6::990004699999 2019.
[85] Y. Wan, A. Naik, and R. S. Sutton. Learning and planning in average-reward Markov decision processes. International Conference on Machine Learning, 2021.
[86] M. Wang. Primal-dual x learning: Sample complexity and sublinear run time for ergodic Markov decision problems. arXiv:1710.06100, 2017.
14

---

[87] R. Wang, D. P. Foster, and S. M. Kakade. What are the statistical limits of offline RL with linear function approximation? International Conference on Representation Learning. 2020.
[88] C.-Y. Wei, M. J. Jahromi, H. Luo, and R. Jain. Learning infinite-horizon average-reward mdps with linear function approximation. International Conference on Artificial Intelligence and Statistics, 2021.
[89] C.-Y. Wei, J. Jahromi, H. Luo, H. Sharma, and R. Jain. Model-free reinforcement learning in infinite-horizz average-reward Markov decision processes. International Conference Machine Learning, 2020.
[90] D. J. White. Dynamic programming, Markov chains, and the method of successive approxima- tions. Math. Anal. Appl, 6(3):373-376, 1963.
[91] Xie, C.-A. Cheng, Jiang, Mineiro, and A. Agarwal. Bellman-consistem pessimism for offline reinforcement learning. Neural Information Processing Systems, 2021.
[92] T. Xie and N. Jiang. Batch value-function approximation with only realizability. International Conference on Machine Learning, 2021.
[93] T. Yoon and E. K. Ryu. Accelerated algorithms for smooth conexx- minimax problems with (11/k2) rate squared gradient norm. International Conference on Machine Learning, 2021.
[94] W. Zhan, B. Huang, A. Huang, N. Jiang, and J. Lee. Offline reinforcement learning with realizability and single-policy concentrability, Conference on Learning Theory. 2022.
[95] Zhang and X. Ji. Regret minimization for reinforcement learning by evaluating the optimal bias function. Neural Information Processing Systems, 2019.
[96] Z. Zhang and Q Xie. Sharper model-free reinforcement learning for average-reward Markov decision processes. Conference on Learning Theory, 2023.
[97] M. Zurek and Y. Chen. Span-based optimal sample complexity for weakly communicating and general average reward MDPs. Neural Information Processing Systems, 2024.
15

---

NeurIPS Paper Checklist
1. Claims
Question:
Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes].
Justification: Our abstract and introduction clearly state the claims made, including the contributions. contributions made the paper
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
is fine to include aspirational goals as motivation as long as is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations the work performed by the authors?
Answer: [Yes].
Justification: Yes, we present limitation of our work as table and discuss in conclusion.
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create a separate "Limitations" section their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g.. independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution is low images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't 't acknowledged judgment and recognize that individual actions in favor of transparency play impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
the paper. The authors should use their best
3. Theory assumptions and proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes].
16

---

Justification:
Yes, we clearly state full set of assumptions and proofs.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated referenced in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but they appear in the supplemental material, the authors are encouraged to provide short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental result reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that affects the main claims and/or conclusions of the paper (regardless whether the code and data are provided or not)?
Answer: [NA].
Justification: Our work does include numerical 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 are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a 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 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 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 large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make clear how to reproduce that algorithm. (b) the contribution is primarily a new model architecture, the paper should describe the architccture clearly and fully.
(c) If the contribution is new model (e.g., a large language model), then there should either way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome to describe the particular way they provide for reprodueibility. the case of closed-source models, may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
17

---

Answer: [NA].
Justification:
Our paper does not include experiments requiring code.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips. cc/
onlooicy))))) for more details.
While we encourage the release of code and data, we understand that this might not be possible, so "No" an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https: / //nips.cooc wwtppppllcggcpcieececeeeooocopce gtte//gggee///eee CCodeSubmiieeeeece
htte:////ggiddee/eeeuuuubiiiiiii wetpommissiiooooooiiioooooo (eionnolccy) for more details.
The authors should provide instructions on data access and preparation, including how 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 subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental setting/details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [NA].
Justification: Our paper does not include numerical 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 to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, or as supplemental material.
7. Experiment statistical significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [NA].
Justification: Our paper does not include numerical 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, confi- dence intervals, statistical significance tests, at least for the experiments that support main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call a library function, bootstrap, etc.)
The assumptions made should be given (e.g.. Normally distributed errors).
should be clear whether the error bar is the standard deviation the standard error of the mean.
18

---

It is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of enrors is not verified.
For asymmetric distributions, the authors should be careful to show in tables or figures symmetric error bars that would yield results that are out of range (e.g. negative eтror rates).
If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of exccution) needed to reproduce the experiments?
Question:
Answer: [NA].
Justification: Ou paper does not include numerical experiments.
Guidelines:
The answer NA means that the paper does include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, cloud provider, including relevant memory and storage.
The paper should provide the amount compute required for each of the individual experimental runs well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary failed experiments that didn't make into the paper).
9. Code of ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics https: //wuunnurrp..// wttpiisss..pppppee
Answer: [Yes].
Justification: Our paper conforms, in every respect, with the NeurIPS Code of Ethic.
Guidelines:
The answer NA means that the authors have reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., there a special consid- eration due to laws or regulations in their jurisdiction).
Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA].
Justification:
Since our work is a theory paper, there is no societal impact of the work
performed.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
19

---

The conference expects that many papers will be foundational research and not tied particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology being used intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms monitor how system learns from feedback over time, improving the efficiency and accessibility of MI..
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA].
Justification: Our 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 to allow for controlled use of the model, for example by requiring that users adhere usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Lieenses for existing assets
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?
Question:
Answer: [NA].
Justification: Our paper does not use existing assets.
Guidelines:
The answer NA means that the paper does 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 a particular source (c.g., website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswi thcode. com com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
20

---

If this information is not available online, the authors are encouraged to reach out to 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: Our paper does not release new assets.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/mmoel as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsoureing 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 details about compensation (if any)?
Answer: [NA].
Justification: Our paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included the main paper.
According the NeurIPS Code of Ethics, workers involved in 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 or equivalent for research with human subjects
Question:
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?
Answer: [NA].
Justification:
Our paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Depending the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and 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 applicable), such the institution conducting the review.
16. Declaration of LLM usage
21

---

Question: Does the paper describe the usage of LLMs if it is important, original, or non-standard component of the core methods this research? Note that if the LLM used only for writing, editing, or formatting purposes and does not impact the core methodology, scientific rigorousness, or originality of the research, declaration is not required.
Answer: [NA].
Justification: Our paper does not involve LLMs as any important, original, non-standard components.
Guidelines:
The answer NA means that the method development in this research does involve LLMs as any important, original, or non-standard components.
Please refer to our LLM policy (https: https///eeuup...eeeee http///rrpss.ccoooeeeeeeeeeeeeee cc//oonfeeeeccs//22511111 for what should or should be described.
22

---

A Prior works
Average-Reward MDP The setup of average reward MDPs was introduced in the dynamic pro- gramming literature by [36], and [9] established theoretical framework for their analysis. In reinforcement learning (RL), average-reward MDP was mainly considered in the sample-bases based setup where the transition matrix and reward are unknown [57, 23]. For this setup, various methods were proposed: model-based methods [41, 97], Q-learning methods [89, 85], and policy gradient methods [5, 62, 46]. Sample complexity to obtain e-optimal under generative model [86, 96, 48, 54, 40] and for regret minimization [15, 38, 95, 11] also have been actively studied.
Value Iteration Value iteration (VI) was first introduced in the dynamic programming literature [6] and serve as a fundamental algorithm to compute the value functions. The sample-based variants, such as TD-Learning [77]. Fitted Value Iteration [25, 61], and Deep Q-Network [58] are the workhorses of modern reinforcement learning algorithms [8. 78, 79J. VI is also routinely applied diverse settings, including factored MDPs [68], robust MDPs [47], MDPs with reward machines [12], MDPs with
options [29), and generative model [84, 75, 48].
The convergence of VI in avcrage-reward MDPs also has been extensively studied. For unichain MDPs, delta coefficient, ergodicity coefficient, and the J-stage span contraction demonstrate the linear rate of VI [74, 37, 27, 81]. When MDP is multichain, it is known that policy error of VI might not converge zero [22, Example 4]. Even with the aperiodicity assumption, VI guarantees only asymptotic convergence. [66, Theorem 9,4.5]. [72, 73J established necessary and sufficient conditions of convergence of VI and asymptotic linear convergence on Bellman error.
Offline Reinforcement Learning In offline RI., the agent learns decision-making strategies utiliz- ing precollected data [53]. This framework is often applied when interaction with the environment can be expensive, and the quantities of data that can be gathered online are substantially lower than the precollected dataset [19, 43, 53]. Consequently, various offline RL methods have been actively proposed [25, 76, 45, 1]. and Fitted Q-Iteration is one of the representative methods based on sample-based value iteration with function approximation [25, 61].
One issue in offline RL is the distribution mismatch between the behavior policy that collected the data and the learned policy of the agent [44, 87J. For theoretical analysis, coverage coefficient is assumed to ensure that offline dataset sufficiently explores whole state and action space. [60, 71, 80]. Under this assumption, sample complexity of offline RI. methods actively analyzed [4, 69, 18, 64), and in particular, an I, bound of approximate value iteration was obtained, which in turn yields convergence results for Fitted Q-Iteration [60, 61]. More recently, several works succeeded relaxing the full coverage assumption to partcal coverage [56, 67, 91, 42).
Another issue offline iL the representation capacity of the chosen function space. To handle large state space and action spaces, many RL frameworks including offline RL use function approximation, ranging from linear functions [24] and nonlinear (general) functions such as neural networks [26] and kernel functions [17]. In offline RL, the inherent Bellman error measures the approximation error incurred when projecting the output Bellman operator into chosen function space, and Bellamn completeness assumes the inherent Bellman error is zero [61, 18]. Most sample complexity analyses in offline RL rely on inherent Bellman error or Bellman completeness assumption [56, 67, 91, 42]. Recently, however, several works achieved finite sample complexity under weaker realizabiltiy assumption, which only requires that optimal function value lies within chosen function space [92, 94].
Most of prior works in offline RL focused on discounted- setup, and to the best of our knowledge, two prior works established the finite sample complexity in the offline average-reward setup [63, 30]. Both proposed a primal-dual approach, reformulating the Bellman equation as bilinear saddle-point problem, to obtain an 6-optimal policy under partial coverage. However, they imposed restrictive structural assumptions on MDP such as uniform mixing or linearity and considered only IID dataset. (See the Table 1.)
23

---

B Preliminaries
The followings are inequalities from prior works used in the proof.
Fact I (Bernstein inequality). Lel X1.-.ry Xn are indepedent random variables. X; S foo all i, then
n²
X, B[X,) 20 seep erp 2
P
2
B
nbc/3
Furthermore, if all the E[X?] are equal, with 1 probability,
X. - EX, S / In(1/)/n 2b 261n(1
3n
Fact 2 ([4), Lemma 4). Suppose that Zi...., Za E Z is a stationary 3-mixing process with mixing
coefficients Bm, 7 E 2(1 E H) are the block-independent ghost samples. H (2ikN + j 0 i mns S kN) and F is permissible class of (-M, , M) functions. Then
N Σ J(Z.. -[((()) >() <
mA 125M + 2m 2m
sup fEF
N
n=1
C
Omitted proofs in Section 3
C.1 Proof of Proposition
Define the limiting matrix P. as the Cesàro limit of pD, p", P matrix always exists for finite state-action spaces [66, Appendix A.4J.) Then, P is stochastic and, by definition, g" = P [66, Proposition 8.1.1J.
lim 1 EE= (PT)'. (The limiting 7
We first prove following lemma.
Lemma 3. Let λK+1 1. Under Assumption 1 (Bellman optimality equation), the policy error of Apx-Anc-QU QI satisfies
gxTx
PP.K(g" -TQ +Q*)
K
I PA
Σ
1e - 24) pr: Σ I m- Ax111 - (m) -1 100 -
1=0
Am IT += ar pptp ) T 1= pr (Ni - -1) ()).
IT
Σ
(mm+1
Proof of Lemma 3. By definition of Apx-Anc-QI, we have
TQ* K -Q"
>x) Q") *x(T** -TQK-1) AKEE
2 (1 - >xx)(TT Q") AKPTK "OK -K-1)- AKEK
2 (1 - -x) - -Q") -KKCK
+ PTT ((Ax Ax )x-1) Q29) + Ax -ATOK-I-TQKeR + AxCK - -K-ICK-1)
k T
K 1 pm: (TQ' - Q*) Σ
AK (".P' T)a
1=0
1=1
where first inequality comes from greedy policy and last inequality comes from induction.
24

---

For any 0 0315 K.
TQ' - -QO
TQ' - Q (Q - )
TQ' TQ + 9" (Q -)
2 pd (Q' + - (Q" Q*.)
= pa, (Ai(TQ) Qah) + (1 11)( - Q=.) ) X1e1) + + - -QT)
X₂ (p=, ( (1 - Am) -1 (Q" - -Q-,) )+ + Σ IT 710
m==
m=0
II (1 cm
where second equality comes from Bellman optimality equation. By combining previous two inequalities, we get
TQK QK
7=14 1:44 AOTT
K
IT
imm++ | Azg
1=0
m=D
Σ 11 - (:p 2m) -1) (00 Q7T)
kkKk ( p
1=0
K
K MIl
1=1+1 (Ri(p - -)et
k 1= ( - P IT (,pr, p mm
1=1 m=1
g
IkK m (1 I m+1 (pt. m
m=
M d (Ni -1) 11) -1)
K
( - -QJII 1 pT
K
Σ
m Ar(1 (p -1 (00 ).)).
0
\m=0
This implies
TQK QK -m
I I - 211 Σ 11/=m41 )=(1 Am (p -1) 1Q"-
K
K Σ (mm+ - Am
Σ
dE
II
m ( + IIK 11 (Xipp)
Finally, following the proof of [66, Theorem 8.5.5], we have
g - TM = P. (g r) = = (g r- pak P + +QK)
= - - + Q*),
25

---

where first equality comes from Bellman optimality equation and second equality comes from property of limiting matrix. This implies that
n"* xxxx = = (g" -TQ +Q*)
< x
Σ
1 -
Σ
m I = 1s
(p).p..)ttmmm (00
K
K
+
II d2
- Am Am) prs ( ( + 11 im i+1 pr (Mip( - -1) a)
The following are lemmas about coverage coefficient CH.pp
Lemma 4. If P1 and P2 are stochastic matrix satisfying p P, S Cp.pl for i = 1,2 and given distribution I and on S x A, then p" (a(PP + (1 aa)22) S for S a S
Lemma 5, Under Assumption (uniform future state distribution).
PT p p ... .......PRR..
sup TT.
Cu.pp
p(-)
where nT T2,... represents an arbitrary sequence of policies with optimal policy.
Proof. Under Assumption 6, for any non negative integer n, we have p T(P=. ja ... pa (.)
Cp.ll. This implies p P..ppa ... p (-) S Cp.pl by definition of limiting matrix.
Lemma IfP stochastic matrix satisfying p S Cappp for given distribution p and p on S x A, then IPQ lp.p < 11m
Proof. Since IPQ(s, a)l² P()- (() S (0t=:))) (s a) by Jensen's inequality, IPQP S p PIQ Cupu IQP.
Now, ready prove Proposition
Proof of Proposition 1. By Lemma 3,
g" - g
K
20 Σ - A1 )m)(pr.)(t -1 -1 1Q0 Q²*))
< P.K
Σ
(0m+1
Am M m pr (p
IT += pa (Ni -1) -1)(a) )1)
Am=l
SPPK
11 Σ
A:(1 Am )m)(P=.)) + +1) 1Q QQ
K
+
>
IT
Σ mmal
(mmt1 - - K
pr (p p ) + IlK 1m 11 prd pr (Nipm + +1) lca)
1=1
Let pp = PKKIIK 1=141 pm (Em Mi 1: - Ap (p. + 1) /2 and P =
P.* IK I (Am+1 ITK
P pni (Ps, )pt.)m+ + 1 pa (Ni 1)/2. Then pf and Pf satisfying pT TPp < Ch.pfi and p pTp Cp for all 0 < < K by Lemma 4 and 5. Thus,
IT m
26

---

have
K
1 -00x> 1l. S 2
Th i=141 A:(Ae41 11)1P/110 - 11pp +2 Σ
n i= >: 1:
1=0
i=1
S / P
Σ
T 2011 QF 1lp,0 2C /p Σ
n delerles
where last inequality comes from Lemma By plugging X = E+2 we conclude. Note that since Cp S Cu.p for any distribution p. then choosing p to be Dirac distribution at each state proves the case of Assumption 5 which implies first inequality of Proposition 1.
L
D Omitted proofs in Section 4
D.1 Proof of Lemma
Proof of Lemma 1. Let F. C [ S A (- mmaz] |f E B(S x A)} and G C {
S x A + 1 9mazz Imaz
f B(S x fet fN cover the F and 9....... ................................ 9N' cover the G
where = Ne:
where S.j ((f.9) = =N(/MMg |11118)): M = 108(R + maz)). x g = US
fillx e, 93 01100 I e). Without loss of generality, suppose
Imar S {max.
First note that 14/-P(11s, (r(s) az) + max g(8) = (g(8s,0)) Ir, + max a(s,a) $ R Sman. [Tg(s, a)l I R + Jmaz.
For arbitrary f F.g G. define X (f(s;, - r(ss max. ا a))² (3; a;) r(s; a.) max, ( a))² Then, (e.aa)n.tt-P((:::a)))
= [[' fll and BI( [_((X/999] s 9(R + 2f 2 [Tg flli.2 since X = (f(s), - Tg(s;, (f a.) + Tg(s;,
2r(s;, a:) 2 max, ( a)), and !X S 33R+ + 2f man)
By Bernstein inequality and union bound, with 8 probability, for all (s+ N.....................
18(R 2f ) ful In(NF
[Tg fill
Exhe9
1:91 1:91//55
V
2(R + 2f I2n
+
where NF.6 = 9.
ll Through 2/ab S a + we have
x figs /n (2 + 25maz) In(Nr,g0))
Af. E.Y E Eg, [[Tg, fill,. -
Σ
1=1
Now, for covering number argument, we use following Lemma.
Lemma 7. For f E F.F.gE 0. [Tg f12..2 -E x/3xx///// / (2 + (2f + R)- Lipchitz.
Proof. Since [T f1ll2.2 - [T fall S (T Tg2 + f2 (T Tg2 fe fill < (1lg) - 92ll + IIʃ - f2ll (2 + 2.fmaz ) [g - 112 is 2(R - 2f Lipchitz. Also,
since >>' x/h.911 /n -E X/2.92 /nl E (max 02 max + fi f2) + ft
max - max 02 2r) (T'g) Tgg + max 92 max 91) (T + + + max + max
2r) < (1lg) - 92 + I f2ll (2 + 255 +
+8 I1 92lloc (Smex + R) < (1lg) g2 ll
||/1 - f2ll )82 (2) + R). En x. 1 /nn 8(25maz + Ri-Lipchitz. By adding two Lipchitz
functions, we obtain desired result.
By Lipchitzness of [Tg, fill
- x! -
/n and definition of covering number, if J.g S
[Tg flli22
x/ x//8/n- ////nn (1 - fill2.2 - 2 > x f1.33 /n) Sc
im1
27

---

This implies that with 1 probability,
F.gge [Tg - fl c 22(R+ + ( +2 +2 x (1)
By other side of Bernstein's inequality and covering number, for all {fis 9j Ji= l M... we have
18(R (ffman)21[[g
fall In(NF,s0))
x fiai / [[ - f.l 1
n
2(R + +-22maaa IIN(F,,/1))
+
1 X /n
4(R+2fmar))
In( (8)
with 1 probability, for all {fi.
a
we have
n
n
x (..00 /n|[T9j - ft 12.22 + 2(R 2f In In(NF
x f:00 /n - &
4.5
i=1
and by ab + b, this implies
4(R + 2fmar) In((F,,))))))
x h: //n - 6.5 - felle.2 S
1=1
Even if Σn X x // 1(R+2fmar) Pn(Ns previous inequality still holds. Since
E X fig /n 6.5l|T St Sill2.2 is 54 + mm Lipshitz, with similar argument, we have
VfEF.ge / 6.5 f11 c 4(R + mf In(NF,g/0)
Let Tg = argmin lEF |lf -Tgl22, and f -T in inequality (2). Then, by definition of Inherent Bellman error.
s.9 /n s c 6.3cg + 4(R + 2fmax) )² In(N=
Vg E g,
Also, let gg in inequality inequality (1). Then, by definition of Tg, have E x < E x T999 Combining with previous inequality, with 1 - 25 probability,
Ag Eg, - - --lll. S + 13c + 30 R + 2a ) (nN
n
Finally, let G = F= Fx+1, and = fk. and by manipulating 5, we get desired result.
D.2 Proof of Theorem
Proof of Theorem 1. By combining Lemma I and Proposition we directly obtain following results. Under assumptions stated Theorem 1, we have
811Q2=-122...
-l - - K 11.0 S C1/2
K +
+ 01/2 01/22K 2K
60(K + R) (2KK3/38)
V3ee
13EB (F,,
3
28

---

811QT 112,
11 - gah 112.0
C112
u.P
K K+2
2K 2K
60(K + +)22
+ C1/2
V3c' +
(Fk, Fx+1))
PuP 3
k= K-1
max
where
Nº max NR.eo k=
= ,....,K. K. NR.e = NI (100(24411 Fk. I1-11oo)) for k = 1,...y
Given
for the first inequality, let K
[18C% 11, /22,//cl,e' 27K²C, n
422
36K Cc 60 (K + 1)² 12)2KN3/0). Then, by direct calculation, derive that max
11g gr llo Set +3KC
k= K-
with sample complexity
112% R
n= O
In( /222//(0)))
c
where
N. = max Niies k= I=....,K K
No.e = N (ookczlie 11, , R Fk. 11-11bo); ), for k = 1....,K. K.
Similarly, given for second inequality, let K /1 Q1Q - 1la.//e,e 27K Cui
162
TV
e (K + 1)2 In(2k and
l1g g TM xx 12, I c 3KC
paP k O...,
max
(FB(FFFFKtt)
with sample complexity
C3 R 11
/1Q 11, 12
n n= 0
u.p 6
where
N = max k=1....K
Nk,e>
Nk.e = N 10 p 10 11, Ri Fas 11-11111o0)
-N
for k = l,..., K.
D.3 Proof of Lemma 2
We first introduce empirical covering number.
Definition (empirical covering number). For given function class F of real valued functions and set pl:n = (I),-- In), denote the covering number of F equipped with the empirical ( pseudo metric Lat (S.9) Ei [fxx)) g(x;)) by (e, x.
Although the empirical convering number depends on number of samples, but can be bounded by pseudo dimension which depends on only function space and following fact shows.
Fact 3 ([35), Corollary 3). For any glm (II,..., In), any function class F of real-valued functions taking values in [0, M) with pseudo-dimension Vx < co, and any e 0,
2ccM Vs
N(e,F, = <(V> e(Vx+1)
Define L(g, f) = Es, (Var, (r(s,, a;) + max f(s/ a))l + 11g Tfll,, where Var denotes variance with respect to s/, and L(g, f) + Er (g(s;, a.) r(s;, ai) max, f(s), a))²
Then, [g f)] L(g. f) and following lemma holds.
29

---

Lemma 8. 1 - f - iinfggg - TT S 2 supgee [Lgg - Lig. f)l-
Proof of Lemma 8. | _ gns 11g T = I(FJ:J) inf geF L(g. L(Tf. L f) f. inf L(g.f) f) S 2supjer L(g. f) LLg. f)l by definition of
For fk, fkk fk] K-1 of Anc-F-QI, previous lemma implies that
[ - 1
inf SEG
inf 1l - T(( 1lg Tíx 12 S sup - T SED
fer
2 sup SEG,JEF
[L(g,f) L(g,
R as 1 (1,11, maxa ( a) and the function space LF.g flig F.9 E g} and Gmar (max, g(s, a) 9 E g). The pseudo dimension of Imaz could be bounded by following Lemma. Lemma 9. Define Gmas {max,e a) g g). Vamas 2|V log(3)A1)-
X Define the function 4g S A Ax
(f(s;, 1
Proof of Lemma 9. By the definition of pseudo dimension, we have Vg 2 Vg: where gi {g(2, a.) g 9)). Since A a); < 0 = Vi (()))) 0, the claim follows from Lemma 3.2.3 of [10].
Now, we ready prove Lemma
Proof of Lemma 2. Let F C (f : SxA - Smaz] |S B(S A)) and G C (g SxA
Imazz 9maz] 1g B(S A)}. Without loss of generality, Imax S fmas.
By similar argument in proof of Proposition of [16), {5,, a, rz) is also 3-mixing with the coefficient { and this implies {5;, ag Ti, $ is also stationary 3-mixing with coefficient {3 By direct calculation, |i(f g)l (25maz + R)2. Now, apply Fact 2 with ((f,g) and Z. (8 0g Ta 81+)). Then, we get
P
sup feFigeg
(.(.9) - I(..0)
(6E (Z)ee)) 128(25max +By +m +2mNBky
THS M
Since
i(hi.g)) i(f2,92) 92)
1
(s)() - r(s,, - - max gi (5)4,,)))))
> (fe(s,) - r(8, (.)
-max (2 (204g)21(111))) a))²
n
aEA
aeA
2 mma + R n a)) f2(s,, a;)l
|max (1 aEA
max
max (2)+,,)))))
aed
this implies that
F,,mm, (im Imary (s, amm (4(22f + R)e, Cr.g, (2 < W(c,F, 2:m+1
where 2 (ss, 0j, ri, 8141) by definition of empirical covering number. Finally, by Fact 3, we get ((e/8,CF.o) (Z)enH)
128(2fmaz + R)e Vz
R)c)
e(VSmon +1) (128(25maz + R)e Vomaz
$ <e(Vs 1)
= -c
Vz+ Vomaaaa
where C= eVF + 1)(V + 1)(128(2fmar + R))e +Vmos For calculation, use following prior result.
30

---

Fact 4 ([4), Lemma 14). Let 3m < Be(-bm"), 2 1, [(C2Ne /b) 14c mm
N/(2kx), 1,, 2 and C₁ C2 B, b, 0. Define e and Co as
Col Co(max{Cor) 1/)2/=
C2N
with C. = Vo2 N log(e/6) + log m ,B,11,
Gi (
402mme2
2m Skx S 6.
ca (c/nax////b11))/
Then, by this fact and previous arguments, for c=
con
P
i(S.9) - I(f.9) 6 SEFi9E9
sup
2 21-8
where cD (Vx + Vg V 1/2 log log(e/8) log(max(ccc, (Vx (omar)) 1/2 3,,1). 16
1)(Vg + () mar mar + DDe2)Vx+Voor Smaz, C2 512(2 RJz: V/moo Vg 1og(3)AAl
Let Fk. F Fk+1 and g fx. By Lemma 8, this implies that with 8 probability,
co (max/(c//bl b,//b,11 1))
[T - f. S EB +
402n
Finally, by manipulating 8, we get desired result.
D.4 Proof of Theorem 2
Proof of Theorem 2. By combining Lemma 2 and Proposition 1, we directly obtain following results. Under assumptions stated in Theorem 2, we have
8 11.,
1 = 100 S C1/2 P
K +
/ 2K
(max(faacco. 13)
Vee(FRe Feri)) (rtt))
max kemO...,h K.
72
11 - 12,0 S 1/2/2 /2/2//0 81 Q 12,1
H.P
K 2
[C.K (maxfcu.K b.kkbb,1 13)1//// 1/4 ((aR (
2IK
2K
+ PiP 3
+ max
C2
k=
where Co.K max C0,6; Co.6
(Vrus V(Frima //2lonn + log(e/(Kō)) log( [g(mmx((c1k) 3, 1)), C1.6 = 16e2 (Vee + 1)(((F))mm + 1)(24e) Yests +Va C2.K 512(2K +I V(Ft)mar = 2|41, VF, log(3/Al).
Given e > 0, for the first inequality, let K = [99 11,me/2 Then, by direct calculation, we derive that
110 TK 11 5 KC1/2 max k=0...KK]
(en(Fe,Fett)
with sample complexity
b (b-l/((b,xx)
1te R$ 18,
12
where 66,x = max K c ca, = log(1/0) + (og(max(eL.,, 8)), = 166
(V(())))er + 1)(22) Vi Via Imas, V(Fz)mar = 2 2|A1, Vr, log(3)Al), and Ô ignores all logarith- mie factors.
31

---

Similarly, given > 0, for the second inequality, let K calculation, we derive that
[9C pup 1QTH 1la,,///e)
Then, by direct
11g" 9 TH a0 E CKK] max
(F,
u.P k= k
with sample complexity
1t R* QQ 112 n= 6 (b-1/M(Cu.x)
C6
M.P
612
where 6, = ma., Ca,er 6a, = log(1/6) + log(max(e1,,,
= 166
(V(FF))) + (24e) V Vi5 V(Fa)mue = 2| Vx, log(3)A)), and Ô ignnors all logarith- mic factors.
E Omitted proofs in Section 5
E.1 Proof of Theorem 3
We first prove following key lemma.
Lemma 10. Assume Assumptions 2, 3, 11, and 12 (Bellman optimality equation, existence of
argmin, star-shaped function space, normalized function space, range of function space, IID dataset). Let p be the distribution generating the dataset. Let 0 and ô > O. With probability (fre fx K-1 of R-Anc-F--OQ satisfies
30(R + 4 10 ) 1n(2222/0) 3e 13En
[T ff S
n
where
N₂ N 10s II.) ll.))
Proof. The proof basically follows from the proof of Lemma 1.
Now, we prove Theorem 3.
Proof of Theorem 3. Consider Apporximate Relative Anchored Value Iteration
= Ax) 2t + (TQ E₁ cc
(Apx-R-Anc-O)
for Ck E R. Also, consider corresponding Approximate Anchored Value Iteration with same 6 and starting point Qo
=1= + +x))
(Apx-Anc-QI)
Since Q² - - 11 for some d4 E R, max, Q* = max, (s, a) for all E S by the defintion of Bellman operator and this implies induced policies same. Thus, Proposition also holds for Apx-R-Anc-6
By combining Lemma 10 and Proposition we directly obtain following results. Under assumptions stated in Theorem 3,
lgg - g S C/1/281QQ2 8T 112,0
K +
2//2 2K
30( R QQ. 2nn
v3e +
/Ice(FFFF)
n
8 81QQ*~112. 112,1
n. -x 11,,p I 01/2
u.p
K +
+ 2122 2K
30(R + QT I1xe) (2K [\1en(FFFF)
V3e'
H.p 3
32

---

where
No. (V 1o8 / Il...) 11-11
Given
0, for the first inequality, let K [18C 110= /12,w/c/,e' 27K n
30K Cp 30(R + 4 QQ" b0 In(2 /6). Then, by direct calculation, we derive that
g 9m 1m c 3KC (cB(F.F
with sample complexity
(R+ 110 1100) 1 1l C
==
In In
where
N₂ W (1= CR _Q 11 11 F, 11.11100))
Similarly, given e > 0, for second inequality, let K = [18C 11Q" 1l
4,2
27K
36K p.e 30( 30
I 1l In(2K"NN://), and
11 TK 112, S 3KC (BB(FFF
with sample complexity
(R (R+ 1Q= 11 )² 1= 11 Ch
= O
In // ((c))
e²
where
N. ( 10 ( ** xx 11 F, 11:11,0)
E.2 Proof of Theorem 4
We first prove following key Lemma.
Lemma 11. Assume Assumptions
9, 10, 11, and 12 (Bellman optimality equation, existence
of argmin, star-shaped function functiion space, normalized function space, range of function space, single- trajectory dataset, B-mixing single-trajectory) Let p be the distribution generating the dataset defined as u(s,a) = (((ss((( s). Let >> 0 and d With probability 1 8. {fk. T fxl of R-Anc-F-Oo satisfies
(maxxfccu (a/ax/cc//brro 1))
[T fflll S (BFFFFFF +
O2n
where oo = (Vz + Vy ) log n/ogn/21 n/2 + log(e/ (K))) + (oa( (c1, B)), 16e (V= Focus (2(24)) +V = 512(1+44 1 V A| log Al).
Proof. The proof basically follows from the proof of Lemma 2.
Now, we prove Theorem 4.
Proof of Theorem 4. By combining Lemma 11 and Proposition 1, we directly obtain following results. Under assumptions stated Theorem 11, we have
11g g 1oc S / 8 8
K +
2/2 2K (
((oo/naxx/ (co(max(co//b, 13)2/02 1/4
+Ven(F,F))
c2n
33

---

11g 10 S C1/2 8T 12,
H.P
+ 2
+ C1/2 2K
((
(co(maxfco/b, 13) 1/4
+ ((B(F,F))
3
C2n
where on. (V++VFmu.. 1/2 log + log (K)) (mw.max(((e) (1 3,1)), -1= 16e (6x2
1)(24)) V V5me C2 512(144114* J Vimus 2 log Al)
Given 0, for the first inequality, let K [90 10T [e. derive that
Then, by direct calculation,
I1g" -=" 10 I e kCP/ (eB(F.F)
with sample complexity
n b b-1/x(c6) 1te (R+ 11 1100)
8
where oj 1og(1/6) + log(max(c) ()),,, (Vz Fmar +2)(2))) Vs + Vimaa =| log(3)_A)), A|), and Ô ignores all logarithmic factors.
Similarly, given e > 0, for the second inequality, K = 190//2 1QT 1l2,//// Then, by direct calculation, we derive that
11g 1bx Set SE+KCUp piP
VEBBFE (F(FFF)
with sample complexity
(R + 1|@ ) 11 Ca.p 1+ 6- (-1//((6)
*
where d) + log(max((1) B)), c 1V= 1VVs + +1)(24)) Vet Vimaz 2/, log(3).Al) and Ô ignores all logarithmic factors.
+
34


Reviews:
[{"review_id": "xJ8IoXCSsd", "reviewer": "Reviewer_Uxsp", "summary": "This paper introduces Anchored Fitted Q-Iteration, a novel algorithm for offline average-reward RL with function approximation. The key innovation is the integration of an anchor mechanism, interpreted as weight decay, into fitted Q-iteration, which enables finite-time convergence analysis under weakly communicating MDPs, a significantly milder assumption than the ergodicity/linearity requirements in prior work.  The paper introduces the first finite-time sample complexity bounds for average-reward offline RL with general function approximation, and improves bounds via Relative Anchored Fitted Q-Iteration, leveraging relative normalization.", "questions": "- Briefly address whether the analysis could extend to partial coverage (e.g., via [91]) under additional assumptions.\n- Can the author briefly discuss the main difficulties of getting an optimal order bound under this setting?", "limitations": "yes", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "**Strengths**\n\n- The paper resolves an open problem by providing the first finite-time guarantees for average-reward offline RL under weakly communicating MDPs. The anchor mechanism is elegantly motivated by Halpern iteration and prior tabular RL work.\n\n- The analysis is thorough, with clear assumptions (e.g., Bellman optimality equation, star-shaped function spaces) and detailed proofs (provided in the appendix).\n\n- The relative normalization mechanism reduces sample complexity by orders of magnitude.\n\n**Weaknesses**\n - Assumptions 5–6 require \"full\" uniform coverage, which is more restrictive than \"partial\" coverage in some prior work. While necessary for the analysis, this limits applicability to datasets with insufficient state-action exploration.\n\n- Despite improvements, the bounds are far away from the optimal order in the offline RL setting. \n\n- No empirical validation: While purely theoretical, ablation studies (e.g., anchor vs. no anchor) on synthetic MDPs could strengthen practical insights.\n\n**some comments**\nAssumption 1  is not necessary; this is the key for solving average reward MDPs.", "was_revised": true, "final_justification": "Based on the discussions, I am inclined to recommend acceptance of the paper.", "rebuttal": "We thank the reviewer for the positive feedback.\n\nQuestions\n\n1. We expect that our anchoring mechanism can provide finite sample complexity guarantees under partial coverage condition by incorporating a pessimistic approach. A series of works [1–3] has shown that penalizing the estimated value or policy according to its uncertainty relaxes the need for full coverage condition. In particular, [3] introduced Pessimistic Value Iteration, which subtracts an uncertainty term scaled by a confidence parameter from the estimated Q‑value, and achieve finite bounds under partial coverage condition. Referring to those prior works, by combining our anchoring mechanism with this pessimistic approach, we believe that our analysis can be extended to the partial coverage setting.\n\n2. In the proofs of our Theorems, we observed that the sample error incurred at each iteration grows proportionally with the number of iterations and  $O(K)$ terms appeared in the upper bound of policy error, where $K$ is number of iterations. In contrast, in the discounted‑reward setting, sum of sample error is bounded by $\\sum_{i=1}^{K}\\gamma^{i}\\epsilon \\le \\frac{\\epsilon}{1-\\gamma}$ where $\\epsilon$ is the per‑iteration sample error (note that the discount factor is considered equal to $1$ in average reward setup). Adding the complexity of Bellman equation, we believe that the sample error in the average reward setup is harder to control. Nevertheless, as we noted in the conclusion, more efficient sample complexity bounds might be obtained by applying variance reduction techniques [4-6] .\n\nSome comments\n\n1. We briefly note that Assumption 1 is valid for weakly communicating MDPs, and a different assumption is needed for multichain MDPs. For multichain MDPs,  the most general class of MDP, it is known that  the Bellman equations consists of two coupled equations and requires more complicated analysis [7]. \n\nReferences\n\n[1] Yao Liu, Adith Swaminathan, Alekh Agarwal, and Emma Brunskill. Provably good batch off-policy reinforcement learning without great exploration. Neural Information Processing Systems, 2020\n\n[2] T. Xie, C.-A. Cheng, N. Jiang, P. Mineiro, and A. Agarwal. Bellman-consistent pessimism for offline reinforcement learning. Neural Information Processing Systems, 2021\n\n[3]  Y. Jin, Z. Yang, and Z. Wang. Is pessimism provably efficient for offline RL? International Conference on Machine Learning, 2021\n\n[4] M. J. Wainwright. Variance-reduced Q-learning is minimax optimal. arXiv preprin arXiv:1906.04697, 2019.498\n\n[5] J. Lee, M. Bravo, and R. Cominetti. Near-optimal sample complexity for MDPs via anchoring. Interantional Conference on Machine Learning, 2025\n\n[6] A. Sidford, M. Wang, X. Wu, and Y. Ye. Variance reduced value iteration and faster algorithms for solving Markov decision processes. Naval Research Logistics, 70(5):423–442, 2023.\n\n[7] M. L. Puterman. Markov Decision Processes: Discrete Stochastic Dynamic Programming. John Wiley and Sons, 2014"}, {"review_id": "ri1gTEclH6", "reviewer": "Reviewer_bu9m", "summary": "The paper considers the task of offline RL in average-reward MDP with general function approximation. In this setting, the authors propose two “anchored” variants of FQI for learning under a much weaker weakly communicating MDP assumption. Their first algorithm, Anchored FQI utilises an anchoring mechanism to stabilise the original FQI update, by mixing $\\hat{f}\\_{k+1}=T^* f\\_{k}$ the $Q^*$ estimate at each step $k$ with the initial guess $f_0$ with a time-dependent mixing parameter. For this method, they prove $O(\\varepsilon^{-6})$, and $O(\\varepsilon^{-10})$ sample complexity guarantees when the offline dataset is generated i.i.d, and from a single trajectory respectively. Lastly, they introduce a  Relative Anchored FQI algorithm, which improves the sample complexity results to $O(\\varepsilon^{-4})$ for the i.i.d setting and $O(\\varepsilon^{-8})$ for the single-trajectory setting, by normalizing $\\hat{f}_{k+1}$ in the Anchored FQI scheme. In contrast to related works, their results all hold under a weaker Bellman completeness condition and strong uniform coverage condition.", "questions": "1. Can the authors comment on why the uniform coverage condition is necessary for the analysis?", "limitations": "NA", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 4, "significance": 4, "originality": 3, "strengths_and_weaknesses": "The paper considers a relevant problem of sample-efficient offline learning in weakly communicating average reward MDPs under general function approximation. To achieve this, they uniquely combine tricks from anchoring – an optimization-inspired mechanism with recent success in RL, and relative VI – a provably convergent VI variant for average-reward MDPs. Yet, the algorithms and sample complexity results are dependent on really strong assumptions. First, both algorithms, like FQI, are oracle-efficient as they will require an optimization oracle to compute the sequence of iterates $\\\\{\\hat{f}\\_{k}\\\\}_{k=0}^{K-1}$. While the focus of the paper is not on computational complexity, such complexity results are equally relevant in MDPs with finitely many states – which is the setting considered in the paper. Second, the sample complexity results depend on strong assumptions such as the uniform coverage – which is less accepted in recent literature even under the general function approximation framework due to needing the behaviour policy to properly explore the entire state-action space.\n\nTo conclude, despite the weaknesses listed above, I would propose acceptance of this paper on the grounds that it indeed is the first (to the best of my knowledge) to establish sample complexity results for average-reward MDPs under general function approximation and with the milder weakly communicating MDP assumption.", "was_revised": true, "final_justification": "I maintain my positive score of the paper as the strengths outweigh the highlighted weaknesses. More so, this work sheds light on the possibility of developing sample-efficient methods for offline learning in weakly communicating average reward MDPs under general function approximation.", "rebuttal": "We thank the reviewer for insightful feedback. \n\nQuestions\n\n1. Our analysis of anchored fitted Q‑Iteration uses the full coverage condition to bound the products of transition matrices induced by policies. As shown in the proof of Proposition 1, the policy error of approximate anchored Q‑Iteration is bounded by a sum of such products with products of coefficients due to the the anchoring mechanism. To control these terms, we exploit the full coverage coefficient and thereby obtain finite sample complexity. We note that this is how standard fitted Q‑Iteration analyses in the discounted reward setting use the full coverage condition [1,2], and lastly, we briefly note that our anchoring mechanism might provide finite sample complexity guarantees under partial coverage conditions by incorporating a pessimistic approach [3-5].\n\nReferences\n\n[1] J. Chen and N. Jiang. Information-theoretic considerations in batch reinforcement learning. International Conference on Machine Learning, 2019.\n\n[2] R. Munos and C. Szepesvári. Finite-time bounds for fitted value iteration. Journal of Machine Learning Research, 2008\n\n[3] Yao Liu, Adith Swaminathan, Alekh Agarwal, and Emma Brunskill. Provably good batch off-policy reinforcement learning without great exploration. Neural Information Processing Systems, 2020\n\n[4] T. Xie, C.-A. Cheng, N. Jiang, P. Mineiro, and A. Agarwal. Bellman-consistent pessimism for offline reinforcement learning. Neural Information Processing Systems, 2021\n\n[5]  Y. Jin, Z. Yang, and Z. Wang. Is pessimism provably efficient for offline RL? International Conference on Machine Learning, 2021"}, {"review_id": "XgAySthzyr", "reviewer": "Reviewer_vmhP", "summary": "This paper analyzes the average-reward RL setting for MDPs with finite state and action spaces. For this setting, the authors propose a variant of the fitted-Q iteration algorithm that uses an anchor to stabilize the iterates generated by the algorithm. Specifically, the anchor amounts to taking a convex combination of an initial iterate and the new estimate of the Bellman optimality operator; the weights of the convex combination are appropriately tuned to achieve finite-time rates. The authors establish sample-complexity bounds under both i.i.d. and single-trajectory, Markovian sampling (with standard mixing assumptions).", "questions": "My questions and comments are listed under \"strengths and weaknesses\".", "limitations": "Yes.", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 2, "significance": 2, "originality": 2, "strengths_and_weaknesses": "**Strengths**\n\n- While there has been a lot of recent work analyzing the infinite-horizon discounted RL setting, analogous results for the average reward case are rarer in the literature. This work takes a step towards closing this gap by considering general function approximators and working under weaker assumptions on the underlying MDP.\n\n- It seems that this is the first paper to analyze the anchored variant of fitted Q-iteration with function approximation. \n\n- Finite-time results are established for the Markov noise setting, which is more challenging to analyze relative to i.i.d. sampling. \n\n**Weaknesses**\n\nI have several comments and questions regarding the nature of the contributions and the assumptions made in the paper. These are outlined below. \n\n- If I understand correctly, based on the discussion in Section 2.1., the idea of anchoring does not seem to be unique to this paper. The idea seems to have been already explored for tabular settings. Is the main algorithmic contribution to extend it to account for function approximators? I would like to have more clarity in terms of what is novel in terms of algorithmic development. \n\n- The assumption that the range of the function classes needs to expand with time (Assumption 7) seems quite strong and non-standard  to me. Can the authors point to any other papers that have made similar assumptions? \n\nThe reason behind making this assumption seems to stem from a crude bound on $ \\Vert f_k \\Vert $ that is on the order of $O(k)$, where $k$ is the iteration count. Can a finer analysis be done to show that $ \\Vert f_k \\Vert $  is perhaps $O(1)$? I presume the sequence ${f_k}$ will eventually converge close to the \"best fit\" function, and as such, its magnitude should not keep increasing linearly with time.\n\n-  The final result in Theorem 1 seems to suggest convergence to a ball of size $O(\\epsilon) + O(K)$ around the optimal state-action value function. My concern is about the second term of order $O(K)$, (where $K$ is the number of iterations) that might make the overall bound vacuous. Since the range of the function classes is required to expand with time, can the authors comment on the magnitude of the term hitting the $O(K)$ term? \n\n- There is no discussion at all regarding the tightness of the sample-complexity bounds derived in this paper. Sample-complexity bounds on the order of $\\tilde{O}(1/\\epsilon^6)$ and $\\tilde{O}(1/\\epsilon^{10})$ under i.i.d. and Markov noise, respectively, seem quite pessimistic (at least compared to what is known in the discounted setting). I would like to see (i) a clear discussion of how these bounds compare with prior results for the average reward setting (even if they are derived under stronger assumptions), and (ii) some discussion of lower bounds/optimality. \n\n- Why is there a substantial gap in the sample-complexity bounds derived for the i.i.d. and Markov settings? For infinite-horizon discounted problems, this gap is only a logarithmic factor that captures the mixing time of the underlying Markov chain; see Bhandari et al., COLT 2018 for instance. In this paper, the gap seems to be on the order of $\\tilde{O}(1/\\epsilon^4)$. Is this just an artifact of the analysis or is there a deeper reason? \n\n- While I appreciate the fact that the authors derived results for the Markov noise setting, similar results do exist for the discounted setting.  For geometrically mixing Markov chains, samples sufficiently spaced out over time are nearly independent, and one can potentially use coupling arguments to translate i.i.d. results to corresponding Markov results. Is there any particular challenge that shows up while handling Markov noise in the average reward case that does not show up for the discounted setting? I would presume not.", "was_revised": true, "final_justification": "The authors provided a detailed rebuttal that addressed all my initial concerns. As such, I am happy to raise my score.", "rebuttal": "We thank the reviewer for the constructive feedback. \n\nWeakness\n\n(i) As the reviewer pointed out, [1,2] have studied the anchoring mechanism in tabular setting. However, it was not known whether the anchoring mechanism provides benefit in the offline RL setting, where only given dataset is available and distribution mismatch between the data distribution and the transition matrices could cause problem. Moreover, it was not clear whether the anchoring mechanism could be incorporated with general function that approximate the output of the Bellman operator in a supervised learning manner. In this paper, we address these questions and, for the first time, establish finite time bounds for the offline average reward setting for both IID and single-trajectory datasets. \n\n(ii) We first note that in the tabular setup, the iterates of Value Iteration (VI) asymptotically behave as $V^k \\sim \\Theta(k)$ as $k \\rightarrow \\infty$ where $V^k$ is $k$-th iterate [3]. Since in our framework, the general function $f_k$ attempts to approximate $V^k$ with offline data, considering the tabular setup as a baseline for the offline setup, we believe that the increasing function range assumption $\\|f_k\\| \\sim \\Theta(k)$ is acceptable. \n\n To address this divergence of the iterates of VI, [4] proposed relative VI which normalizes the iterates by subtracting a uniform constant vector at each iteration. Motivated by this, we propose Relative Anchored Fitted Q-Iteration with function range assumption, specifically assuming $\\|f_k\\| \\sim \\Theta(1)$, and as shown in Theorems 3 and 4, we obtained finer sample complexities $\\tilde{O}(\\epsilon^{-4})$ and $\\tilde{O}(\\epsilon^{-8})$ for IID and single-trajectory dataset, respectively.\n\n(iii) As reviewer pointed out, in our Theorems 1 and 2, the policy error is bounded by a given $\\epsilon$ and an $O(K)$ term containing the coverage coefficient and inherent Bellman error, where, by condition of Theorem, $K$ is fixed if $\\epsilon$ is fixed. We note that if the inherent Bellman error is low or the approximation power of the function class is strong enough, this term can be relatively small. Or, it can be ignored under the Bellman completeness assumption, which assumes that the inherent Bellman error is zero. These assumptions, low inherent Bellman error and Bellman completeness, are commonly used in the RL theory literature [5, 6]. Furthermore, we believe this $O(K)$ term in the theoretical upper bound is natural in average reward analysis (please refer to response (v)).\n\n(iv) The reviewer raises a good point. We first note that in section 5, we presented Relative Anchored Fitted Q-Iteration and further obtained refined sample complexities of $\\tilde{O}(\\epsilon^{-4})$ and $\\tilde{O}(\\epsilon^{-8})$ for IID and single-trajectory datasets. Also, to the best of our knowledge, there exist two prior works that studied the sample complexity in this setup. [7] and [8] obtained $\\tilde{O}(\\epsilon^{-2})$ and $\\tilde{O}(\\epsilon^{-4})$ sample complexities for IID datasets under ergodic and unichain MDPs, respectively, and our Theorem 3 provides a $\\tilde{O}(\\epsilon^{-4})$ sample complexity for IID datasets under weakly commuting MDPs. But none of prior works address single-trajectory datasets.\n\nAs far as we know, there exist no lower bound results in the offline average reward setting. Hence, it is subtle to argue the tightness and optimality of our sample complexity results. However, reflecting optimality results in the discounted reward setup, we expect that our results may be tight or close to optimal sample complexity with respect to $\\epsilon$. To be more precise, we speculate that the optimal sample complexity of the average reward setup would be the square of the optimal sample complexity of the discounted reward setup.\n\nIn the discounted reward setup, [9, 10] established a $\\tilde{O}(\\epsilon^{-2})$ lower bound on sample complexity for IID datasets, and several works achieve optimal sample complexity. For the single-trajectory dataset, to the best of our knowledge, there exist no lower bound results, but [11] establishes $\\tilde{O}(\\epsilon^{-4})$ sample complexity. Considering the technical difficulty in the average reward setup (please refer to response (v)), we carefully expect that our sample complexity results in the average reward setup, $\\tilde{O}(\\epsilon^{-4})$ and $\\tilde{O}(\\epsilon^{-8})$ for IID and single-trajectory datasets, which are exactly the squares of the sample complexities in the discounted reward setup, $\\tilde{O}(\\epsilon^{-2})$ and $\\tilde{O}(\\epsilon^{-4})$, would be tight or close to optimal. But, as we said, a lower bound in the offline average reward setting remains unknown, and studying optimality in this setup would be an interesting research direction.\n\n(v) To the best of our knowledge, in the discounted reward offline RL setting, there exists an $\\epsilon^{-2}$ gap between IID and mixing single-trajectory datasets. Roughly speaking, [5] provides a sample complexity $\\tilde{O}(\\epsilon^{-2})$ for an IID dataset, whereas [11] proves a sample complexity $\\tilde{O}(\\epsilon^{-4})$ for a mixing single-trajectory dataset. This discrepancy arises from the different concentration inequalities used in the analyses. In particular, [5] applies Bernstein’s inequality, while [11] uses Pollard’s tail inequality generalized to mixing single-trajectory data, and Pollard’s tail inequality yields looser bounds than Bernstein’s inequality. This induces an $\\epsilon^{-2}$ gap between IID and mixing single-trajectory datasets. \n\nTurning to the average reward setup, in the proofs of our Lemmas 5 and 11, we also apply Bernstein’s inequality and the generalized Pollard inequality. Thus, similarly, we have an $\\epsilon^{-2}$ gap. But, moreover, an additional gap occurred for the following reason: in the discounted reward setup, the sum of sample errors is bounded by $\\sum_{i=1}^{K}\\gamma^{i}\\epsilon\\le \\frac{\\epsilon}{1-\\gamma},$ where $\\epsilon$ is the per-iteration sample error. However, in the average reward setup, where the discount factor is considered equal to $1$, we get $O(K)$ bound on the sum of sample errors proportional to the number of iterations by $\\sum_{i=1}^{K}\\epsilon \\le K\\epsilon.$ This caused an additional gap in the average-reward setup, and consequently, our results exhibit an $\\epsilon^{-4}$ gap, which is the square of the $\\epsilon^{-2}$ gap in the discounted reward setup.\n\nLastly, [12] indeed establishes a sample complexity $\\tilde{O}(\\epsilon^{-2})$ for both IID and single‑trajectory datasets. However, that paper studies a different setting from ours in two respects. First, Algorithm 1 performs online updates, sampling state and action in real time, so its theoretical analysis does not require the coverage condition that offline RL usually needs to address the distribution shift [5,11]. Second, the paper considers the policy evaluation problem of estimating $V^{\\pi}$ for a given policy $\\pi$, whereas we study the policy control problem of finding the optimal policy $\\pi^{\\star}$.  We think that the different results follow from different setups. \n \n(vi) First, we clarify that our work does not assume a mixing MDP for either the IID or single‑trajectory setting.  Actually, we assume only that the single-trajectory dataset, generated by a specific behavior policy, is mixing. As noted in the introduction, a mixing MDP requires the mixing condition to hold for every policy and initial distribution, whereas our mixing assumption requires it to hold only for the behavior policy and the distribution of the dataset.  Thus, our mixing assumption on single-trajectory datasets is much weaker than the mixing assumption on the MDP, and therefore, sample complexity results in the discounted reward setting under mixing Markov chains do not imply our results in either the IID or single-trajectory setting. \n\nWe kindly ask that the reviewer consider raising the score if our answer addresses their concerns and questions.\n\nReferences\n\n[1] J. Lee and E. Ryu. Accelerating value iteration with anchoring. Neural Information Processing Systems, 2023.\n\n[2] J. Lee and E. Ryu. Optimal non-asymptotic rates of value iteration for average-reward MDPs International Conference on Learning Representations, 2025.\n\n[3]  M. L. Puterman. Markov Decision Processes: Discrete Stochastic Dynamic Programming. John Wiley and Sons, 2014\n\n[4] D. J. White. Dynamic programming, Markov chains, and the method of successive approximations. J. Math. Anal. Appl, 6(3):373–376, 1963.\n\n[5] J. Chen and N. Jiang. Information-theoretic considerations in batch reinforcement learning. International Conference on Machine Learning, 2019.\n\n[6] A. Zanette, A. Lazaric, M. Kochenderfer,  E. Brunskill,  Learning near optimal policies with low inherent bellman error. International Conference on Machine Learning 2020.\n\n[7] A. Ozdaglar, S. Pattathil, J. Zhang, and K. Zhang. Offline reinforcement learning via linear programming with error-bound induced constraints. arXiv preprint arXiv:2212.13861, 2024.454\n\n[8] G. Gabbianelli, G. Neu, M. Papini, and N. M. Okolo. Offline primal-dual reinforcement learning for linear MDPs. International Conference on Artificial Intelligence and Statistics, 2024\n\n[9] G. Li, et al. Settling the sample complexity of model-based offline reinforcement learning. The Annals of Statistics 52.1 (2024): 233-260.\n\n[10] P. Rashidinejad, et al. Bridging offline reinforcement learning and imitation learning: A tale of pessimism. Advances in Neural Information Processing Systems 34 (2021): 11702-11716.\n\n[11] A. Antos, C. Szepesvári, and R. Munos. Learning near-optimal policies with bellman-residual minimization based fitted policy iteration and a single sample path. Machine Learning, 2008.\n\n[12] J. Bhandari, D. Russo,  R. Singal. A finite time analysis of temporal difference learning with linear function approximation. Conference on learning theory, 2018."}, {"review_id": "1b1kDe5Vqz", "reviewer": "Reviewer_s4WQ", "summary": "This paper presents the first finite-sample complexity results for offline reinforcement learning (RL) in the average-reward setting with general function approximation. The authors propose a novel algorithm, Anchored Fitted Q-Iteration (Anc-F-QI), which introduces an anchoring mechanism-akin to weight decay-to ensure finite-time convergence.\n\nThey derive sample complexity bounds for two scenarios:\n1. IID data: $\\tilde{O}(1/\\epsilon^6)$\n2. Single-trajectory data (with $\\beta$-mixing): $\\tilde{O}(1/\\epsilon^{10})$\n\n\nTo improve these bounds, the authors propose a normalized variant, Relative Anchored Fitted Q-Iteration (R-Anc-F-QI), which further improves the bounds to:\n1.  IID: $\\tilde{O}(1/\\epsilon^4)$\n2.  Single-trajectory: $\\tilde{O}(1/\\epsilon^8)$\n\n\nAll results are derived under the mild and general assumption that the underlying MDP is weakly communicating, extending beyond the ergodic or unichain assumptions used in prior work.", "questions": "1. Why is the weakly communicating assumption less restrictive than ergodic or unichain assumptions? What practical implications does this have?\n  2.  What role does the anchoring mechanism play in ensuring finite-time convergence in the average-reward setting?\n  3.  How does the normalization in R-Anc-F-QI (relative version) improve sample complexity compared to standard Anc-F-QI?\n  4.  How does the sample complexity change under IID vs.  single-trajectory data? What causes the higher complexity in the latter case? \n  5.  How critical is the full-coverage assumption for the derived bounds? Could the results extend to partial-coverage settings without sacrificing generality?\n  6.  Are there known practical scenarios or benchmarks where average-reward RL is preferable to discounted-return RL, justifying the relevance of this work?", "limitations": "Yes", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 2, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths\n  1. Provides the first finite-time sample complexity guarantees for average-reward offline RL under weakly communicating MDPs.\n  2. Works under more general conditions than prior literature (e.g., ergodic or unichain MDPs).\n  3.  Introduces an anchoring mechanism within fitted Q-iteration and a normalization technique that improves convergence.\n  4.  Achieves better bounds with the normalized variant (R-Anc-F-QI).\n  5.  Clearly states all assumptions and provides complete theoretical proofs.\n  6.  Includes a concise comparison with prior work, highlighting improvements.\n\n\nWeaknesses\n  1. The paper lacks experiments, limiting insights into the practical performance of the proposed methods.\n  2.  Assumes full state-action coverage in offline datasets, which is difficult to guarantee in practice.\n  3.  The paper is mathematically dense and may be difficult for non-experts to follow.\n  4.   Realistic implications of assumptions (e.g., $\\beta$-mixing, Bellman completeness) are not deeply explored.\n  5.  Requires Bellman completeness to ensure zero inherent Bellman error, which may not hold with general function approximators.", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for detailed feedback. \n\nQuestions\n\n(i) Intuitively speaking, a weakly communicating MDP requires that one policy be good, whereas a unichain MDP requires every policy to be good. By definition [1], an MDP is weakly communicating if there exists a policy for which set of states where every state in the set is accessible from every other state (plus a possibly empty set of transient states), and an MDP is unichain if, for all policies, the induced Markov chain has a single recurrent class (plus a possibly empty set of transient states). As we clarified in the introduction, this difference induces that a weakly communicating MDP guarantees the Bellman equation only for the optimal policy, while a unichain MDP satisfies the Bellman equation for every policy. In this sense, weakly communicating assumption is less restrictive than ergodic or unichain assumption, and many practical algorithms have been developed for various settings of weakly communicating MDPs [2,3].\n\n \n(ii) Roughly speaking, in the anchoring mechanism, the anchor term pulls the iterates toward the starting point, and this gives the effect of acceleration in convergence. In the fixed‑point literature, it is known that when the anchoring mechanism is combined with fixed‑point iteration, it effectively reduces the residual error. Recently, [4,5] have shown that anchoring indeed provides accelerated rates and efficient sample complexity in the average reward setup. In our analysis, the anchoring mechanism ensures sublinear convergence with respect to both the Bellman error and the policy as shown in the proof of Proposition 1, and this lead to first finite time bounds for  weakly communicating MDPs.\n \n(iii) The role of relative normalization in R‑Anc‑F‑QI is to bound the norm of the function approximator, $\\|f_k\\|$, from diverging, as our function space range assumption states. Compared to Anc-F-QI, this normalized technique leads to efficient sample complexity. This is because, in the theoretical analysis, we used Bernstein’s and Pollard’s inequalities, whose upper bounds are proportional to the square of $\\|f_k\\|$. Thus, R‑Anc‑F‑QI improves sample complexity, as we showed in Theorems 3 and 4.\n\n\n(iv) As the reviewer pointed out, our theorems show that the sample complexity of an IID dataset is more efficient than that of a single‑trajectory dataset. We believe that this discrepancy arises because the inequalities we applied differ in the analysis. As shown in the proofs of Lemmas 5 and 11, we used Bernstein’s inequality for the IID dataset and Pollard’s tail inequality generalized to mixing data for the single‑trajectory dataset, and Pollard’s tail inequality yields looser bounds than Bernstein’s inequality. Consequently, the sample complexity for a mixing single‑trajectory dataset is less efficient than for an IID dataset. We briefly note that this gap also exists in the discounted‑reward offline RL setting [7,8].\n\n\n(v) Our analysis of Anc-F-QI uses the full coverage condition to bound the products of transition matrices induced by policies. As shown in the proof of Proposition 1, the policy error of Approximate Anchored Q‑Iteration is bounded by a sum of such products with products of coefficients due to the anchoring mechanism. To control these terms, the full coverage is needed and this is how standard Fitted Q‑Iteration analyses in the discounted reward setting use the full coverage condition [7,9].\n\n We expect that our anchoring mechanism can provide finite sample complexity guarantees under partial coverage condition by incorporating a pessimistic approach. A series of works [10–12] has shown that penalizing the estimated value or policy according to its uncertainty relaxes the need for full coverage condition. In particular, [12] introduced Pessimistic Value Iteration, which subtracts an uncertainty term scaled by a confidence parameter from the estimated Q‑value, and achieve finite bounds under partial coverage condition. Referring to those prior works, by combining our anchoring mechanism with this pessimistic approach,  we believe that our analysis can be extended to the partial coverage setting.\n\n(vi) For continual or infinite‑horizon tasks where long‑term performance is significant, the average reward setup is a preferable alternative to the discounted reward setup [13-15]. Specifically, average reward framework suits problems like robotic locomotion [16] and queuing systems [17], and many practical RL algorithms have been studied for this setup [18,19].\n\nReferences\n\n[1] M. L. Puterman. Markov Decision Processes: Discrete Stochastic Dynamic Programming. John Wiley and Sons, 2014\n\n[2] Bartlett, Peter L., and Ambuj Tewari. REGAL: A regularization based algorithm for reinforcement learning in weakly communicating MDPs. arXiv preprint arXiv:1205.2661 (2012).\n\n[3] Wan, Yi, and Richard S. Sutton. On convergence of average-reward off-policy control algorithms in weakly communicating MDPs. arXiv preprint arXiv:2209.15141 (2022).\n\n[4] J. Lee and E. Ryu. Optimal non-asymptotic rates of value iteration for average-reward MDPs International Conference on Learning Representations, 2025.\n\n[5] J. Lee, M. Bravo, and R. Cominetti. Near-optimal sample complexity for MDPs via anchoring. Interantional Conference on Machine Learning, 2025. \n\n[6] D. J. White. Dynamic programming, Markov chains, and the method of successive approximations. J. Math. Anal. Appl, 6(3):373–376, 1963.\n\n[7] J. Chen and N. Jiang. Information-theoretic considerations in batch reinforcement learning. International Conference on Machine Learning, 2019.\n\n[8] A. Antos, C. Szepesvári, and R. Munos. Learning near-optimal policies with bellman-residual minimization based fitted policy iteration and a single sample path. Machine Learning, 2008.\n\n[9] R. Munos and C. Szepesvári. Finite-time bounds for fitted value iteration. Journal of Machine Learning Research, 2008\n\n[10] Yao Liu, Adith Swaminathan, Alekh Agarwal, and Emma Brunskill. Provably good batch off-policy reinforcement learning without great exploration. Neural Information Processing Systems, 2020\n\n[11] T. Xie, C.-A. Cheng, N. Jiang, P. Mineiro, and A. Agarwal. Bellman-consistent pessimism for offline reinforcement learning. Neural Information Processing Systems, 2021\n\n[12]  Y. Jin, Z. Yang, and Z. Wang. Is pessimism provably efficient for offline RL? International Conference on Machine Learning, 2021\n\n[13] Sutton, R. S., Barto, A. G. (1998). Reinforcement learning: An introduction. Cambridge: MIT press.\n\n[14] Mahadevan, S. (1996). Average reward reinforcement learning: Foundations, algorithms, and empirical results. Machine learning, 22(1), 159-195.\n\n[15] Naik, A., Shariff, R., Yasui, N., Yao, H., Sutton, R. S. (2019). Discounted reinforcement learning is not an optimization problem. arXiv preprint arXiv:1910.02140.\n\n[16] Kober, J., Bagnell, J. A.,  Peters, J. (2013). Reinforcement learning in robotics: A survey. The International Journal of Robotics Research, 32(11), 1238-1274.\n\n[17] Schneckenreither, Manuel, Stefan Haeussler, and Juanjo Peiro. Average reward adjusted deep reinforcement learning for order release planning in manufacturing. Knowledge-based systems 247 (2022): 108765.\n\n\n[18] Hisaki, Yukinari, and Isao Ono. RVI-SAC: average reward off-policy deep reinforcement learning. arXiv preprint arXiv:2408.01972. 2024\n\n[19] Zhang, Yiming, and Keith W. Ross. On-policy deep reinforcement learning for the average-reward criterion. International Conference on Machine Learning. 2021."}]

Author rebuttal:

Meta-review: This paper develops a new algorithm, Anchored Fitted Q-Iteration, for offline average-reward RL. The key innovation is the integration of an anchor mechanism, interpreted as weight decay, into fitted Q-iteration, which enables finite-time convergence analysis under weakly communicating MDPs, a significantly milder assumption than the ergodicity/linearity requirements in prior work. The paper introduces the first finite-time sample complexity bounds for average-reward offline RL with general function approximation, and improves bounds via Relative Anchored Fitted Q-Iteration, leveraging relative normalization. Some weaknesses are also noted during the review: strong assumptions of full coverage in offline setting, lack of experiments, loose sample complexity bounds.
Decision: Accept (poster)