A Computationally Efficient Algorithm for Infinite-Horizon Average-Reward Linear MDPs
Authors: Kihyuk Hong
Ambuj Tewari
Venue: ICML 2025 poster (2025)
Keywords: reinforcement learning theory
infinite-horizon average-reward RL
linear MDP
Primary area: theory->reinforcement_learning_and_planning
TL;DR: First computationally efficient algorithm for infinite-horizon average-reward linear MDPs.

Abstract: We study reinforcement learning in infinite-horizon average-reward settings with linear MDPs. Previous work addresses this problem by approximating the average-reward setting by discounted setting and employing a value iteration-based algorithm that uses clipping to constrain the span of the value function for improved statistical efficiency. However, the clipping procedure requires computing the minimum of the value function over the entire state space, which is prohibitive since the state space in linear MDP setting can be large or even infinite. In this paper, we introduce a value iteration method with efficient clipping operation that only requires computing the minimum of value functions over the set of states visited by the algorithm. Our algorithm enjoys the same regret bound as the previous work while being computationally efficient, with computational complexity that is independent of the size of the state space.

A Computationally Efficient Algorithm for Infinit--orizon Average-Reward Linear MDPs
Kihyuk Hong'
Ambuj Tewari
Abstract
definitions of long-term rewards. The first is the infinite- horizon discounted setting, where the objective is to maxi- mize the discounted cumulative sum of rewards, with expo- nentially decaying weight assigned to future rewards. The second the infinite-horizon average-reward setting, where the objective is to maximize the undiscounted long-tew term-temm average of rewards, assigning uniform weight future and present rewards. Learning in the average-reward setting is more challenging because its Bellman operator is not con- traction, and the widely used value iteration algorithm may fail when the transition probability model used for value iteration is not well-behaved. This complicates algorithm design, especially when the underlying transition probability model is unknown and must be estimated.
We study reinforcement learning in infinite- horizon average-reward settings with linear MDPs. Previous work addresses this problem by approximating the average-rewand reward setting by dis- counted setting and employing a value iteration- based algorithm that uses clipping to constrain the span of the value function for improved statisti- cal efficiency. However, the clipping procedure requires computing the minimum of the value function over the entire state space, which is pro- hibitive since the state space in linear MDP setting can be large or even infinite. In this paper, we in- troduce a value iteration method with efficient clipping operation that only requires computing the minimum of value functions over the set of states visited by the algorithm. Our algorithm en- joys the same regret bound as the previous work while being computationally efficient, with com- putational complexity that is independent of the size of the state space.
Seminal work by Auer et al. (2008) introduces value it- eration based algorithm for the infinite-horizon average- reward setting in the tabular case, where the state space and the action space are finite. To address sensitivity of the value iteration algorithm to the transition probability model, they maintain a confidence set that captures the true, well-behaved transition probability model. Their algorithm employs extended value iteration approach, which op- timally selects the transition probability model from the confidence set at each iteration. This extended value itera- tion method has since been extensively used in the tabular setting (Bartlett & Tewari, 2009; Fruit et al., 2018; Zhang & Ji, 2019). Beyond the tabular case, the method has also been adapted the linear mixture MDP setting (Modi et al., 2020; Ayoub et al., 2020), where the transition probability model has low-dimensional structure (Ayoub et al., 2020; Wu et al., 2022; Chae et al., 2025).
1. Introduction
Reinforcement learning (RL) aims to learn optimal actions for an agent by interacting with the environment. Among the various RL. settings, the infinite-horizon setting partic- ularly well-suited for applications where optimizing long- term performance is the primary objective. Examples in- clude production system management (Yang et al., 2021; Gosavi, 2004), inventory management (Gijsbrechts et al., 2022; Giannoccaro & Pontrandolfo, 2002) and network rout- ing (Mammeri, 2019), where interactions between the agent and the environment continue indefinitely, and the natural goal is to optimize long-term rewards.
To our knowledge, the extended value iteration method is limited to tabular and linear mixture MDPs, as relies on sample-efficient transition probability estimation, which is infeasible for settings like linear MDPs with large state spaces (Jin et al., 2020). In response to these limitations, researchers have explored alternative approaches for such settings. For example, Wei et al. (2021) propose a reduction to the mnite-horizon episodic setting by dividing the time steps into episodes a fixed length. This approach achieves a regret bound of (TT3/4), which is suboptimal, where T denotes the number of time steps. They also introduce a
In the infinite-horizon framework, there are two widely-used
Department of Statistics, University of Michigan, Ann Arbor, US. Correspondence to: Ambuj Tewari <tewaria unuch.edu>.
Proceedings of the 4nnd International Conference Machine Learning. Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).

---

Infinite-Horizon Average-Reward RL
policy-based algorithm that alternates between policy eval- uation and policy improvement steps directly optimize the policy. This approach achieves order-optimal regret bound of (VT), but it requires a strong ergodicity assump- tion on the transition probability model for sample-efficient policy evaluation. Lastly, they propose another approach that achieves an order-optimal regret bound by directly solv- ing the Bellman optimality equation as a fixed point problem, bypassing the need for value iteration. However, the fixed point problem is computationally intractable.
the Bellman optimality equation directly as fixed-point problem, which is computationally intractable, with brute- force solution requiring computational complexity that scales with T", where d is the dimension of the feature representation. OLSVLFF reduces the problem to the finite- horizon episodic setting. This approach is computationally efficient, but has suboptimal regret bound. LOOP general- izes FOPO to the general function approximation setting, but inherits the computational complexity that scales with T for solving a fixed-point problem. MDP-EXP2 directly optimizes for the policy by alternating between policy eval- uation and policy improvement. This approach is com- putationally efficient and achieves an order-optimal regret bound, but requires a strong assumption that all policies induce Markov chains that have uniformly bounded mixing time. 7-LSCVI-UCB reduces the average-reward problem to the discounted problem and achieves an order-optimal regret bound. However, its computational complexity scales with the size of the state space S. Our work is the first com- putationally efficient algorithm to achieve ((VT) regret without making strong assumptions.
Another line of work on infinite-horizon average-reward RL uses a reduction to the discounted setting to leverage value iteration- basedd algorithms. To our knowledge, Wei et al. (2020) were the first to introduce such a method. They propose a Q-learning-
algorithm for the tabular setting that solves the discounted setting problem as surrogate for the average-reward problem, achieving a regret bound of (332/3). More recently, Hong et al. (2025) propose a value iteration based algorithm that clips the value function to constrain its span for statistical efficiency, achieving an order-optimal regret bound of Ö(VT). Their algorithm runs value iteration to generate a sequence of value functions to plan for the remaining time steps, and takes actions greedy with respect to the value functions until certain information criterion of the collected trajectories doubles. Although the algorithm runs in polynomial time with respect to problem parameters, its computational complexity depends on the size of the state space. The dependency is undesirable in the linear MDP setting where the state space can be arbitrarily large. An open question arising from this line of work is:
Approximation by discounted setting The method of approximating the average-reward setting by the discounted setting has been used in various settings. It is used in the problem of finding a nearly optimal policy given access to a simulator in the tabular setting by Jin & Sidford (2021); Wang et al. (2022); Zurek & Chen (2023); Wang et al. (2023). It is also used in the online RL setting with tab- ular MDPs: Wei et al. (2020) propose a Q-learning based algorithm, but has (TT2/3) regret. Zhang & Xie (2023) im- prove the regret to ((VT) by making use of an estimate for the span of optimal bias function. The reduction is also used in the linear mixture MDP setting by Chae et al. (2025).
Does there exist an algorithm for infinite-horizon reward linear MDPs with computational complexity polynomial in the problem parameters, yet independent of the size of the state space?
Span-constraining methods Learning in the infinite- horizon average-reward setting requires an assumption that ensures the agent can recover from a bad state, Ieading to a bounded span of the optimal value function. For statistical efficiency, previous work makes use of this fact by con- straining the span of the value function estimates. Bartlett & Tewari (2009) modify the extended value iteration algo- rithm by Auer et al. (2008) to constrain the confidence set on the model so that the spans of the models in the set are bounded. Fruit et al. (2018) propose a computationally effi- cient version of the algorithm proposed by Bartlett & Tewari (2009). Zhang & Ji (2019) improve the algorithm proposed by Bartlett& & Tewari (2009) by constructing tighter confi- dence sets using a method for directly estimating the bias function. Zhang & Xie (2023) study a Q-learning- based algorithm that projects the value function to function class of apan-constrained functions. Hong et al. (2025) and Chae et al. (2025) propose a value iteration- based algorithm and clips the value function to constrain its span.
In this paper, we answer the question in the affirmative by proposing an algorithm based on the following novel techniques.
Efficient Clipping We develop an efficient value function clipping strategy that requires the minimum of the value function to be evaluated only over the set of states visited by the algorithm, rather than the entire state space.
Deviation-Controlle Value Iteration We introduce a novel value iteration scheme that controls the deviation between sequences of value functions generated by value iterations with different clipping thresholds.
1.1. Related Work
Table compares our work with previous approaches for infinite-horizon average-reward linear MDPs. FOPO solves
2

---

Infinite-Horizon Average-Reward RL
Table 1. Comparison of algorithms for infinite-horizon average-reward linear MDP
Algorithm
Regret (()
Assumption
Computation poly())
FOPO (Wei al., 2021)
sp(v") dT
Bellman optimality equation
T A,, T,A, d A,,,d
OLSVLFH (Wei ct al., 2021)
v ss((U) (dT)
Bellman optimality equation
LOOP (He et al., 2024)
sp(u") J d d mis" T sp(v") VdTT TT
Bellman optimality equation Uniform Mixing
MDP-EXP2 (Wei et al., 2021)
T.A.d
7 LSCVII-UCB (Hong al., 2025)
Bellman optimality equation
T,S,A,
>-DC-LSCYI-UCB (Ours)
sp(r") VoTT TeT
Bellman optimality equation
T,A,d
Lower Bound (Wu et al., 2022)
M(d//p(vv*)
2. Preliminaries
the interaction between P and
Notations Let ||م|| = Vx Ar for æ E R and posi- tive semi-definite matrix A E Rdxd Let aVbb = maxfa. b} and a A b min(a, 6). Let ( be the set of probabil- ity measures on X. Let [n] = (1.....n) n} and [m n)
The performance of an algorithm interacting with the en- vironment over T steps is evaluated through its regret rela- tive the best stationary policy n' that maximizes J (s1). Writing J (s1) J (81), the regret after T steps is de- fined
{m, m + +I,...... ......n.. Let sp(e) = m (u(s) - v(6)).
Let CLI (1 (LV
T
RT = ((r(ss) - r(s,
2.1. Hnfinite-Horizon Average-Reward RL
E=1
The interaction protocol for the infinite-horie horizon setting, un- like the interaction protocol for the finite-horizon episodic setting, the state is never reset. Consequently, if the agent en- ters a bad state with low future reward and recovering from the bad state and reaching good state is impossible, then the agent becomes trapped in the bad state and suffers regret linear in the number of remaining time steps. As discussed by Bartlett & Tewari (2009), an additional assumption on the structure of the MDP is required to avoid the patholog- ical case. At the very least, we want the gain J' to be constant: (s)(s = J for all 8 E S. This implies no matter what the current state is, following the optimal policy x attains the optimal long-term average reward J', precluding the of getting trapped in bad state. We follow Wei et al. (2021) and make the following structural assumption the MDP.
In this section, we formulate the infinite-horizon average- reward RL setting. We pose the RL problem as a Markov decision process (MDP) M = A, P.)) where S is the state space, A is the action space, P S A + ASS) is the probability transition kernel and r S A - R is the reward function. We assume that rewards are bounded in [0, 1]. a standard and mild assumption that can be enforced by rescaling. We assume S is a measurable space with possibly infinite number of elements and A is a finite set. The deterministic reward function is known the learner while the probability transition kernel P is unknown to the learner.
The interaction protocol between the learner and the MDP as follows. The environment first reveals the starting state 81 the learner. Then, at each time step = 1, 2...., the learner chooses an action ag E A and receives the reward rsse, at). The environment transitions to the next state 8 sampled from a()).
Assumption A (Bellman optimality equation). There exist J RR and functions v" such that for all (s,a) E S x A. we have
IR and q" S A R
In the infinite-hoiizon average-reward setting, the perfor- mance of a policy is evaluated using the long-term average reward. Consider a stationary policy æ : S - ((A) where (als) denotes the probability of choosing action a in state The average reward of policy starting from an initial state s is defined as
J + q (s, [s a) = r(s, a) + [PE*](s,a)
(((s) max q" (s) aeA
As shown by Wei al. (2021), tuple (J", .9", v²) that satis- fies the equations in the assumption above has the following properties. The policy " that deterministically selects an action from argmax, qs a) at each state s E S is an op- timal policy. Moreover, such x² always gives an optimal average reward J (s) = J for all initial states e S. Since the optimal average reward is independent of the ini-
(s) = iim Ex 7-0 T
Σ r(st, a:)
where the expectation [-] is taken over the probability distribution on the trajectory (81, a1, 82, ......) induced by
3

---

Infinite-Horizon Average-Reward RL
tial state, we can simply write the regret as
discounted sum should approach average of the reward se- quence. To make this intuition precise, we first define value functions for a policy x under the discounted setting by
T RT= = 1- az)).
The functions (s) and q-( (s, a) have the interpretation of the relative advantage of starting with and (s, a), re- spectively, and are called bias functions. A pair of func- tions (v", q") that satisfies the Bellman optimality equa- tion is v² (s) o ET
(T()) E
/ ((se, me)|s1 =
(7(,,)= = E"
Σ 7 r(s,, de)ss 05 5, - -
D r(5r; 0t) [s s] and 9¹ (s. a) = lim E" EEEIT r(s,, at) - J 81
N
We write the optimal value functions under the discounted setting as
5, 01 = a). Remark 2.1. The Bellman optimality equation assump- tion is weaker than the weakly communicating assumption, which states that the state space can be partitioned into a set of transient states, which the agent never revisits once it leaves, and a set of recurrent states, where the agent can reach any state from any other under some policy. In turn, the weakly communicating assumption weaker than the ergodic assumption, which requires that for every policy, the induced Markov chain is irreducible and aperiodic.
V (8) = max VT (s), (7 a) = max Q77 (s.
x
Previous informal discussion suggests that the normalized value function (1 V1 (s) to be close to the gain under the average-reward setting J The following lemma makes the relation between the infinite-horizze average-reward setting and the discounted setting formal.
Lemma 2.3 (Lemma 2 in Wei al. (2020)). For any Y E (0, 1). the optimal value function V for the infunite-horizon discounted setting with discounting factor ry satisfies
The span of the bias, sp(u") = max.,s'es v" (s) (d'), quantifies the worst-case difference in value between any two states. Intuitively, entering suboptimal state incurs regret that scales with sp(v"), suggesting that problems with large sp(e") are more challenging to learn. Following pre- vious work (Bartlett & Tewari, 2009; Wei et al., 2020), we assume sp(e*) is known to the learner. This assumption can be relaxed by instead assuming access to an upper bound on sp(="). but in this case, the regret of our proposed algorithm will scale with the upper bound.
(i) sp(V)) S 2sp(w") and
(i)
- for all E S.
The lemma above suggests that the difference between the optimal average reward J and the optimal discounted cu- mulative reward normalized by the factor (1 7) is small as long as 7 is close to 1. Hence, we can expect the policy optimal under the discounted setting will be nearly optimal for the average-reward setting, provided y is sufficiently close 1.
Remark 2.2. Whether sample-efficient learning is possible without knowing the span in advance has been an open question for a long time, and many existing works rely on this assumption. A recent result by Boone & Zhang (2024) shows for the first time that it be avoided in the tabular setting. However, extending their technique to the linear MDP setting remains significant challenge and likely require a major breakthrough. We leave this to future work.
2.3. Linear MDPs
The linear MDP setting is a widely-studied setting in RL theory literature that allows sample efficient learning in large state space by assuming low-dimensional feature representation of the state-action pair. This representation allows for generalization to unseen states, yielding sample complexity that is independent of the size of the state space. The linear MDP model imposes the following structural assumptions on the MDP:
2.2. Infinite-Horizon Discounted Setting
The key algorithm design employed in this paper is to approximate the infinite-horizon average-reward setting by the infinite-horizon discounted setting with a discount- ing factor > [0, 1) chosen by the learner. Under the discounted setting, the performance measure is the dis- counted sum of rewards Σ - at). When nor- malized by factor (1 - 7), the resulting normalized dis- counted sum is weighted average of the reward sequence r(s,, a,), rS22, (2), a ..... The decay rate of the weight se- quence is governed by the discounting factor y. As ap- proaches 1, the decay becomes slower and the normalized
Assumption B (Linear MDP (Jin et al., 2020)). We assume that the transition and the reward functions can be expressed as a linear function of known d-dimensional feature map <p S x A + Rd such that for any (s. E S x A, we have r(s, a) = a)(ss,),0), P(8'(s,a) (spss, a), (())))
where (uss)= = (((()))..,,(((s))) for E S is a vector of d unknown measures on S and O E Rd is a known parameter for the reward function.
4

---

Infinite-Horizon Average-Reward RL
we further assume, without loss of generality, the following boundedness conditions:
Algorithm I 1-LLCCV-UCC (Hong et al., 2025)
Input: Discounting factor 7 E [0, 1), regularization con-
[|sp(s, a)ll for all a) E 8 x A,
stant À > span H > 0, bonus factor > 0.
(1)
Initialize: < 1, l4 +- 1, A < AI, QH (s. + 1-7 for
|00|2 - vd, (|x(S) S Vd.
L E [7].
Such a boundedness assumption is commonly made, without loss of generality (Wei et al., 2021), when studying the linear MDP setting.
1: Receive state $1.
2: for time step = l....., do do
3: Take action a - argmax, Qi a).
Remark 2.4. Wei et al. (2021) show that the boundedness assumption can be made without loss of generality with the following reasoning. Given a parameterization O and y for the reward function, Il1 I 1. Then, they show there exists an invertible transformation A _dd + IRd such that the minimum vol- ume enclosing ellipsoid (MVEE) of A J (-A0) is a unit ball. A transformed feature mapping (s(s,a) = Ap(s, a) and a transformed parameter 6' A 4 leads the same reward function with ||0'||2 1, as desired. As discussed by Wei et al. (2021), this transformation depends only the feature mapping s, not on the parameter 8, and can thus be applied during the feature design stage As shown in Theorem 8 of Hazan & Karnin (2016), computing such a transformation takes time ( + ())S)AA)).
4: Receive reward r(se; at): Receive next state 81+1-
5:
t A + (s( ar (s(e))(sss at)".
6:
if det < det(A,) then
rescale 0 and ip such that
7:
I E- k+ 1, 4. e- ++1.
8:
(24()) + --
9:
for u = T,
1,...,t do 0,-1(,)) + (r(s)) + ((Pr, +
10:
(.+)
+3)1v((-))1A r
11:
V++1()) + max. (s.aa
12:
vi++() + CLIP(V
minges Ve+1 (s'), minges Vi-1 (s') + H). end for
13:
14:
else
15:
0++1 + 2 VL+1 +- Vt for E [t + 1: 1:
16: end if
As discussed by Jin et al. (2020), although the transition model P is linear in the d-dimensional feature mapping s, P still has |S] degrees of freedom as the measure I is unknown, making the estimation of the model P difficult. For sample efficient learning, we rely on the fact that [PV](s, a) is linear in cp(s, a) for any function V + R so that (sV] a) (sp(s, w) where w" (V) = fwes ((s') Indeed,
17: end for
2.4. Previous Work
In this section, review the closely related work of Hong et al. (2025) to highlight the contributions of our paper. They propose an algorithm, 3-LSCVI-UCB (Algorithm 1), which is an optimistic value iteration based algorithm for infinite-horizon average-reward linear MDPs. At time step 4, a sequence of value functions Q/ -: Qt is com- puted by running value iterations (Line 8-13) to plan for the best action time considering the number of time steps remaining. In the next time step t + 1, instead of running value iteration again to incorporate new transi- tion data observed at time step t, the algorithm reuses the value function Qi+1 generated previously. Value iteration is only rerun when the determinant of the covariance matrix A; =I + Σt=1 (p(ss, at (() az) doubles (Line 6).
[pV] Sres ((dsssds')s.
= Sses V (s))))p(s,.), = (pp(s (ds)))
Exploiting the linearity, we can estimate un (V) given a trajectory data (s1, ,.,..., 81-1, a1-1, 8t) via linear regres- sion as follows:
(v) = AJ Σ ((s++1) ((6t+))-<p(s,,0))
where A,- = A E ((s), ( regression coefficient, we estimate [PV] by
st, T. With such a
Clipped Value Iteration A key ingredient of the algo- rithm is the value clipping step, which constrains the span of the value function estimate to improve statistical effi- ciency. The optimal value function V, under the discounted setting has span bounded by 2 2 ssp("") (Lemma 2.3), which implies the range V is contained in the interval [min.es V,, (s), min.es V + 2 -p((")). Building on this fact, the algorithm clips the optimistic value function es- timate V to the interval [minges (s). minges ((s) + H] to constrain its span (Line 7). We refer to the lower bound
(s.V] a) = (p((s, a), (V - V(si)) + (si).
We estimate (s, a) by estimating [P(V - (ss)))ssss a) and then adding back (s1).. This allows bounding the norm of the regression coefficient || |w, (V- -V VVss)) by a bound that scales with the span of V instead of the magnitude of V, which is required for getting a sharp regret bound. A similar technique used by Hong et al. (2025).
5

---

Infinite-Horizon Average-Reward RL
of this interval of the clipping operation as clipping thresh- old. The clipping ensures that the concentration bound for the estimate (PV](.)) -) scales with sp(o*), rather than --q+ which is crucial for obtaining a tight regret bound.
With unlimited compute power, the --L-CV----UU algo-
rithm by previous work uses min,es v++ (8) the clipping threshold, which allows bounding V441 evaluated at 8 by
Key Step of Regret Analysis In their regret analysis, one of the terms in the regret decomposition is
V (8441) -CLI(VELL( (+), min Vi+1()) H)
RES SES
Σ Vi (8 - V441 (8441).
(144((0411)
where the inequality only holds because min.es V (s) s ( The algorithm 7-LLCVI--CBB also reuses the sequence of value functions most of the time steps, such that V (56+1) = V41
This term can be bounded using the fact that Vi4i (5t+1) 1 V ($141), and that Vi ($ V/41 (5++1) whenever the same sequence of value functions is used for the time steps and & + 1. Since the sequence of value functions is only updated when the covariance matrix A, doubles, which can be shown to happen only Od T) times, we can get a tight regret bound.
W ( allowing the bound
V (8++1) V (*++1) S 0.
For computational efficiency, suppose we use me as the clipping threshold instead of minses Vi+ (s), where m is computed using states s 8t only. Then, the bound (8c+1) S V (8441) may no longer hold because
Computational Complexity However, their clipping step (Line 7) requires taking the minimum of the value function estimate (-) over the entire state space S, leading to com- putational complexity linear in the size of the state space, which can be prohibitive when the state space is large or infinite. The main contribution of our paper addresses this issue by designing an algorithm that only takes the mini- mum over the states that have been visited by the learner, removing the dependency of the size of the state space on the computational complexity. As discussed in the next section, additional algorithmic trick is required for control- ling the deviation of sequences of value functions generated under different clipping thresholds.
(1+4()11)) = CLIP(V/ (1:4+))::: ma, me + H) 2 mi
and we may have m. > Vi41 ($c+1) since we cannot look ahead 8141 when choosing the clipping threshold my. We can instead get a bound with an error term:
V (8++)) =
my + H)
I <V441 + max(m, ((44)))))
One key idea of handling the sum of the error terms is to choose m = ((41( A m, (Line 15), leading to
3. Algorithm Design and Analysis
(5 S V (5(41) +
In this section, we present our algorithm, discounted Deviation Controlled Least Squares Clipped Value Iteration with Upper Confidence Bound (7-DC-LCCV--CC,, Algo- rithm 2). which improves computational complexity of the previous algorithm. The part of the proposed algorithm that enables computational efficiency is highlighted in red.
where A, m, M++1- Then the sum of the errors A can then be bounded using telescoping sum.
The clipping threshold m4+1 = Vit (8++1) A m, may change every time step. Hence, after advancing to the next time step t + and computing the new threshold me+1, the algorithm computes Q'+} afresh, which involves generating a sequence of value functions V by running clipped value iteration with the new thresh- old m4+1- Therefore, unlike previous work that ensures ((41)) = / ($++1) by reusing the sequence of value functions, we need to control the difference between Ve Ve (8441) and V441 ( to be able bound
3.1. Computationally Efficient Clipping
V441
The algorithm design is centered around bounding the term
T-1
Σ
Vi Ve41 (8(41);
where (Vihejt: is the sequence of value functions gen- erated at time step f, and [e is the sequence of clipped value functions generated at time step t. Note that the clipped value function ViA1 in the summation is gener- ated at time step i, prior to observing the next state 8141-
Vi (+441) S V Vi (8++1) + A Ro +1 (8++1) + Ac-
The next section discusses the algorithm design for ensuring Vi Ri V.++1
6

---

Infinite-Horizon Average-Reward RL
Algorithm 2 7-DC-LSCVI-UCB
Then, by value iteration, we have
Input: Discounting factor y E [0. 1) regularization con- stant À A> 0, span > 0, bonus factor B >
I 1lo0 I - 2-- lloo 2 [|P((V u+ v *
ll
Initialize: A1 f- AI, m- 1 t 0o, mo t- 00, m1 f- 1-
It is natural to expect that || Vutille S A would imply |I - VoTi)l S A. This true when (s,)) is an expectation of V(-) with respect to an empirical probability distribution Pt(-,.-), which is the case for the tabular setting (see Appendix B.1 for more discussion). However, in the linear MDP setting, and more generally in general value function approximation setting, [s. a) is defined through regression: [P,V] (s, a) (g(ss, a), we Vz a+1 v=+1)), which can be arbitrarily larger than as shown the next lemma.
( f- 1 T- Qu (.)) - T-
1: Receive state $1.
2: fort = I....,Td. do
3: (+) c I
4: for u ===T, I....o
5: (.())) - ((()) + (( (
+ 11
1
1-7'
6:
U.()) 2 Q ( (+)).
7:
(Qth (v.) m4-1 m+)
Lemma 3.1. There exist -1:-.., . On E Rd with || S for i = 1, I,..., n, and yı,...,, ,//n E IR with lual S A, i 1,..., for any A > O, such that
v(QU u
( ((,)) M4-2 me).
8:
Ql(:))) CLIP(Q ); U,,,,,)))
9:
Vi(()) <- max, (;)))
10:
(i(() < CLIP(V m4; m, + H).
1(w Φ
2 Avv
11:
end for
for some Φb E IRd where wn is the regression coefficient
Take action ar + argmax, Qi(st, a).
W0, A, E yids where A,, = = Φ: + AI.
13: Receive reward r(s,, az). Receive next state $141-
14:
A4+1+ < A₁ + sp(t, at ax)sp(8t,aa)
To address this issue. we propose novel value iteration procedure that explicitly controls the deviation of sequence of value functions from its previous sequences. The key idea is to clip the value function Q so that its values do not deviate too much from value functions Q and Q1-2 from previously generated sequences of value functions (Line 6- 8). With this scheme, we can bound the difference between V and / as follows.
15:
M +- ( A Ame.
16:
end for
3.2. Deviation-Controlli Value Iteration
Previous discussion suggests we need to bound the differ- ence between sequences of value functions {V huer and (V++1) [ue]]] generated by value iterations using different clipping thresholds m, and m4+1- We would expect that the difference between sequences of value functions to be bounded by the difference in clipping thresholds m, M++1- Surprisingly, naive adaptation of the previous work 7 LSCVI-UCB, fails to control the difference. To see this, consider the following clipped value iteration procedure that generates a sequence of value functions (Vi) J time step t using the clipping threshold m,-
Vu
Lemma 3.2. When running 7-DC-LSCVI-CCB (Algo- rithm 2), we have
(++1(s) - [((( S m - m
for all t E [T], u E [t: T and for all s E S.
The lemma above says that the sequence of value functions [V++1) Jue[t+1:T] generated at time step + 1 deviates from the chain of value functions [ by at most m,-1 m4+1- This deviation control enables bounding the term Σ (( - (S141), which we demonstrate in the next section.
(++ & 1 for u = T,T - I,...,,t do (++)-) + (r(,-) + ((
+Bllo(, ))laa+)))) +
3.3. Regret Analysis
(T()) < max ()) Vi(()) C m. H).
In this section, we outline regret analysis for our algorithm. Central to the regret analysis is the following concentration bound for the estimate P.V.
end for
Lemma 3.3. With probability at least 8, there exists an absolute constant c2 such that for B C. Hdd//og(dd (8).
We argue that controlling the difference | - V241 lloo s A for A = Mc+1 at value iteration index u++ does not necessarily control the difference V Vi+1Il Il at the next
[P.V - [[VV a)l S _11
value iteration. To see this, suppose [ 1otlllos S A.
for all t E [T], u E [t: T) and (s.0) E S A
7

---

Infinite-Horizon Average-Reward RL
A proof for the lemma above first finds concentration bound for P.V for fixed value function : IR using concentration bound for vector-valued self-normalized processes. Then, an é-net covering argument is used to get uniform bound on the function class that captures all value functions Vi encountered by the algorithm. For this to work, we require the function class to have low covering number. We can show that the log covering number of the function class that captures functions Qi can be bounded by (dP), which amounts to covering the d x d matrices A, Since Q is function of 5 functions in this function class, the log covering number of the function class that captures Q is bounded by (dP). With the concentration inequality, and the fact that the algorithm uses B)|sp(,, A))l as the bonus term, we get the following results.
Bounding (a) By the optimism result (Lemma 3.4), we
have (s) 2 (*(s) for all t E (T) and u E [t T] with
high probability. It follows that
J (1 (1 - V4 " J (1-
I <1-7)ssp(o")
where the last inequality is by the bound on the error of approximating the average-reward setting by the discounted setting provided in Lemma 2.3. Hence, the term (a) can be bounded by T(1 - >))p(("))
Bounding (b) Using Lemma 3.2 that controls the differ- ence between V741 and Vi, we have
(5 ( me, my + H)
Lemma 3.4 (Optimism). With probability least 1 8, for all t E [T] and u E [t: I] and E S, we have
< CLIP(V/41 (+++1) m4+1, m441 + H) + my M4+1
3 (144() + my - m
(s(s) 2 (s).
- 241 (st+1) + +22m-1 2m++1
where the second inequality holds because V ($t+1) 2 m4+1 by Line 15. Hence, term (b) can be bounded by O (1LT)) using telescoping sums of V441 (8++1) - Vg((s))
as long as the input argument I1 is chosen such that H 2
2 . sp(x").
Lemma 3.5. With probability at least 1 - 8, we have for all
and 2m;-1 - 2m,+1, and the fact that V I T and my S - T for all t E [7] and [t:
t E [4: T) and u E [t: T) that
(x, S (s,,a) a) + IVV
+ 2 a)l + 2(m me)
Bounding (c) Since V is F--mesuurblle where F, is history up to time step t, we have 1
[ (e)), making the summation (c) a summation of martingale difference sequence. Since sp(V44)) < H for all t E [T]. the summation can be bounded by (ss((o*) TT) using Azuma-Hoeffding inequality.
for all (s,a) E S x A.
Using the lemma above, the regret can be bounded by
Rr [J r(st, az))
Bounding (d) The sum of the bonus terms can be bounded by ((3/dT) using standard analysis from literature on linear MDP.
< E
- (J"
(iss, at) + + az)
+ (/ a:) Ils, + 2(m4-3 - m+)) + 0(1)
Combining the bounds, and choosing = 2 sp(v") and 8 = ((s((e")d) specified in Lemma 3.3, we get
which can be decomposed into
(1 V2)22
Rr S Õ >))p((")) + 1_ +
(a)
+ s ) (3T).
+ Σ -== (8441)) - (s.))
Choosing 7 = leading to our main result (see Appendix C for more detailed analysis):
VI/T, we get RT S (sp((')) VdTT),
(b)
T
([PVitllssna)) - ((++1))
Theorem 3.6. Under Assumptions A and B, ranning Algo- rithm 2 with inputs = 1 1011-11/110 vI/T, x= H = 2 sp(e") and 20g sp(u") /lo(/) guarantees with proba- bility at least 1 5,
223 Er (1)(s)))))la, + 0 1
O
(d)
RT O(s((v)) V d (TTlog(d)) /8) log T).
where we use (s, at) = (s)) by the choice of az by the algorithm. Each term can be bounded as follows.
where e3 is defined in Lemma 3.3.
8

---

Infinite-Horizon Average-Reward RL
The regret bound for our algorithm 7-DC-LSCVI-UCB matches the regret bound of the previous algorithm "-- LSCVI-UCB.
Impact Statement
This paper presents work whose goal is to advance the field of Machine Learning. There are many potential societal consequences of our work, none which we feel must be specifically highlighted here.
Remark 3.7. Both algorithms DCC-LSCVI and "-- LSCVI-UCB require the knowledge of the time horizon T to tune the discount factor y in order to achieve T-step regret bound of O(vT) This limitation can be addressed using the standard doubling trick, which allows to obtain regret bound of (VTT) for any horizon T.. The doubling trick is a standard technique in online learning to convert an algorithm with (vVT) regret guarantee for fixed known T' to an anytime algorithm that does not take T as an input and guarantee 7 ttpp regret of (VVT) for any T. The idea is to the algorithm in phases, where each phase lasts twice long the previous one. At the beginning of each phase, the algorithm is restarted with parameters tuned for that phase length.
References
Abbasi- Yadkori, Y., Pál, D., and Szepesvári, C. Improved algorithms for linear stochastic bandits. Advances in neural information processing systems, 24, 2011.
Auer, P., Jaksch, T., and Ortner, R. Near-optimal regret bounds for reinforcement learning. Advances in neural information processing systems, 21, 2008.
Ayoub, A., Jia, Z., Szepesvari, C.,, Wang, M., and Yang, L. Model-based reinforcement learning with value-targeted regression. In International Conference on Machine Learning, pp. 463-474. PMLR, 2020.
3.4. Computational Complexity
Our algorithm 7-LSCVI-UCB+ runs up to T steps of value iteration every time step, resulting in O(T2) value iteration steps. This can be seen by the nested loop structure of the algorithm, where the outer loop indexed by for the time step and the inner loop is indexed by u for the value iteration step. The computational bottleneck of the algorithm is computing Q (s, a) for all A and all E {si....,8:.- .. which involves computing the regression coefficient w. (V++ (V++1). Computing the regression coefficient takes O(T + d operations.
Bartlett, P. and Tewari, A. Regal: a regularization based algorithm for reinforcement learning in weakly commu- nicating mdps. In Uncertainty in Artificial Intelligence: Proceedings of the 25th Conference, pp. 35-42. AUAI Press, 2009.
Boone, V. and Zhang, Z. Achieving tractable minimax opti- mal regret in average reward mdps. In The Thirty-eighth Annual Conference on Neural Information Processing Systems, 2024.
In total, the computational complexity of our algorithm is Of A), which is polynomial in the problem parameters T, d, A and is independent of the size of the state space. Although our algorithm enjoys polynomial-time compu- tational complexity, it is super linear in T, just as the the OLSVI.F algorithm (Wei et al., 2021) and the previous work --LCCVI-UCB (Hong et al., 2025). We leave further improving the computational complexity to be linear T as future work.
Chae, W., Hong, K., Zhang, Y., Tewari, A., and Lee, D. Learning infinite-horizon average-reward linear mixture mdps of bounded span, 2025.
Fruit, R., Pirotta, M., Lazaric, A., and Ortner, R. Effi- cient wlas-span-constraime exploration-explootaaion in reinforcement learning. In International Conference on Machine Learning, pp. 1578 PMLR, 2018
Giannoccaro, I. and Pontrandolfo, P. Inventory manage- ment in supply chains: reinforcement learning approach. International Journal of Production Economics, 78(2):
4. Conclusion
153-161, 2002.
We propose an algorithm for sefinite-horizon average-reward RL with linear MDPs that achieves a regret bound of (sp((v") Vdd()) and is computationally efficient. Our al- gorithm uses a combination of techniques such as approx- imation by discounted setting, value function clipping for constraining its span, and deviation-controlles value iter- ation. An interesting future directions include improving the regret bound by factor of vd using variance-aware regression method, extending the techniques to the general function approximation setting, and learning a stationary policy for memory efficiency.
Gijsbrechts, J., Boute, R. N., Van Mieghem, J. A., and Zhang, D. J. Can deep reinforcement learning improve inventory management? performance lost sales, dual- sourcing, and multi-echelon problems. Manufacturing & Service Operations Management, 24(3):1349-1368 2022.
Gosavi, A. Reinforcement learning for long-run average cost. European journal of operational research, 155(3): 654-674, 2004.

---

Infinite-Horizon Average-Reward RL
Hazan, E. and Karnin, Z. Volumetric spanners: an efficient exploration basis for learning. The Journal of Machine Learning Research, 17(1):466244055, 2016.
Yang, H., Li, W., and Wang, B. Joint optimization of pre- ventive maintenance and production scheduling for multi- state production systems based on reinforcement learning. Reliability Engineering & System Safety, 214:107713, 2021.
Hc, J., Zhong, H., and Yang, Z. Sample-efficient learning of infinitehhrizonn average-reward mdps with general function approximation. In The Twelfth International Conference on Learning Representations, 2024.
Zhang, Z. and Ji, X. Regret minimization for reinforce- ment learning by evaluating the optimal bias function. Advances in Neural Information Processing Systems, 32, 2019.
Hong, K., Chae, W., Zhang, Y., Lee, D., and Tewari, A. Re- inforcement learning for infinite-horizon average-reward linear mdps via approximation by discounted-reward mdps. In International Conference on Artificial Intel- ligence and Statistics, 2025.
Zhang, Z. and Xie, Q. Sharper model-free reinforcement learning for average-reward markov decision processes. In The Thirty Sixth Annual Conference on Learning The- ory, pp. 5476-5477. PMLR, 2023.
Jin, C., Yang, Z., Wang. Z., and Jordan, M. I. Provably effi- cient reinforcement learning with linear function approxi- mation. In Conference on learning theory, pp. 2137-2143. PMLR, 2020.
Zurek, M. and Chen, Y. Span-based optimal sample complexity for average reward mdps. arXiv preprint arX1:2231..1346,, 2023.
Jin, Y. and Sidford, A. Towards tight bounds the sam- ple complexity of reward mdps. In Interna- tional Conference on Machine Learning, pp. 5055-5064. PMLR, 2021.
Mammeri, Z.
Reinforcement learning based routing in networks: Review and classification of approaches. leee Access, 7:55916-559501 2019.
Modi, A., Jiang, N., Tewari, A., and Singh. S. Sample com- plexity of reinforcement learning using linearly combined model ensembles. In International Conference Artifi- cial Intelligence and Statistics, pp. 1010-20200 PMLR, 2020.
Wang, J., Wang, M., and Yang, L. F. Near sample-optimal Inluction-based policy learning for average reward mdp. arXiv preprint arXiv:2212 2212222.00000 2022.
Wang, S., Blanchet, J., and Glynn, P. Optimal sample complexity for average reward markov decision processes. arXiv preprint ar 2tt.:231100883333 2023.
Wei, C.-Y., Jahromi, M. J., Luo, H., Sharma, H., and Jain, R. Model-free reinforcement learning in average-reward markov decision processes. Interna- tional conference on machine learning, pp. 10170-10180. PMLR. 2020.
Wei, C.-Y., Jahromi, M. J., Luo, H., and Jain, Learning infinite-horizan average- reward mdps with linear function approximation. In International Conference on Artificial Intelligence and Statistics, pp. 3007-3015. PMLR, 2021.
Wu, Y., Zhou, D., and Gu, Q. Nearly minimax optimal average-reward mdps
regret for learning with linear function approximation. In International Con- ference on Artificial Intelligence and Statistics, pp. 3883- 3913. PMLR, 2022.
10

---

Infinite-Horizon Average-Reward RL
A. Concentration Inequalities
Lemma A.1 (Concentration of vector-valued self-normalized processes (Abbasi-Yadkee) et al., 2011)), Let {Er)
real-valued stochastic process with corresponding filtration {F.]E=o- Let F, be zero-mean and o-subgaussian. Let - be an IR. -valued stochastic process where de Fi-1- Assume Ao d d positive definite matrix, and let Ae Au Ex=1 0.02. Then for any 8 > O, with probability at least 1 - 5, have for all 2 0 that
dee((e))) 11/2
E&E
$202log
AT
Lemma A.2. Let un be ridge regression coefficient obtained by regressing y E [0, B) on a Rd using the dataset (( 9i) so that A----- Ei= aiti where A -Ei=1 xxx + Xl. Then,
11l12 S dn/A.
Lemma A.3. Let V S B) be bounded function. Then, w (V) Ss v(s)dpp(ss) which satisfies [PV[ a)(s,a), w (V)) for all (s, S A, satisfies
1| (V)ll2 S Bvd.
Proof.
1/ V())) v(d)du(()))
SB B BBIs duls)) S Bvd
100 1 (V)
where the first inequality holds since fa is a vector of positive measures and V(8) 2 0. The last inequality is by the boundedness assumption (1) on (SS).
Lemma A.4 (Adaptation of Lemma D.4 in Jin et al. (2020)). Let {xt]i= be a stochastic process on state space S with corresponding filtration {Fi)e Let f be a valuud stochastic process where Oi Fi-1. and || f 1. Let
An AI + Σi= diØT. Then for any 5 > 0 and any given function class V. with probability at least for all and any V E V satisfying sp(V) H, we have
[d.
(++A)
No
8n2e²
Σ
BV)
S 4H² log
+ log +
where Ne is the E-covering number of V with respect to the distance dist( V, V') = sup (xx)-
Lemma A.5 (Adaptation of Lemma B.3 in Jin et al. (2020)). Under the linear MDP setting in Theorem 3.6 for the --LSCVI- UCB algorithm with clipping oracle (Algorithm 1), let ca be the constant in the definition of 3 = cy Hd log(dT) (8T There
exists an absolute constant C that is independent of eg such that for any fixed 6 (0, 1), the event defined by
Yu E [T), t T
Σ
(s a, (PV C Hel HHdyloo((ess 18)
A-
satisfies P(E)= 2 -
...,,. for any & > 0 and any fixed pair (u,t) E [T] x (T). we have with probability at least 5/T² that
Hence, by combining Lemma D.3 and Lemma A.4, Proof. By Lemma A.2, we have |/,1112 < H HH/dl dt// for all 1= 1,.... T.
Σ (s a -
(PV
A
2
(t+}) 2
4H Vdt dt eVA
8d /2 1+
T
8t?
< 2
log
+ dlog
1+
+d
loo
d
εZ
A

---

Infinite-Horizon Average-Reward RL
Using union bound over (u,4) E [T] [T] and choosing & Hd/1 and X 1, there exists absolute constant C independent of es such that, with probability at least -
Σ ((s,, - a+)l
SC dl 1f + 1)dT
A
which concludes the proof.
A.1. Proof of Lemma 3.3
Proof of Lemma 3.3. We prove under the event & defined in Lemma A.5. Recall the definition
P.V = (40 a), VV (=)))) + (1))
where V.(V u
(s()) = A, A (V - (s1)) ( ar). For convenience, we introduce the notation (i)() = (s) - (s1) and w = (V.( With these notations, we have
[P.V = (10(8, w + (s1), wt = A, E (p ar az)
We can decompose (sp(s, a), w as
(p)(s w ((((s a), A, Σ ((s,, a,) PV)llsss)))) + (p((s,)) A, E a (V
(s. ar))
(b)
Since (x) E |- H] for all 8 E S, it follows by Lemma A.3 that w| (Vi)ll2 & H Hvd. Hence, the first term (a) in the display above can be bounded as
t-1
a),s Σ pl,, a (PV = (p((s, a), A
Σ
(p(s(( at (r)(p()))ssa... w/)="" (V.))
(4((s, w (V() X/p(8, a), A, (Vi)) S (1p(s, a). w (V.) + Allp(s,a))la || (VillA s (00(s, a), w" (VD) + H ppss a)]l
where the first inequality is by Cauchy-Schwart and the second inequality is by Lemma A.3. Under the event & defined in Lemma A.5, the second term (b) can be bounded by
(p(ss, a), AT
Σ p(s ar (V)((++1)
(PV.]
< 1|p(s, 3x - -
N-1
C Hd log((cs + 1)dT/() /11((s)))ll)) [|d1/
Combining the two bounds and rearranging, we get
(Ø, 1t, w (V+) S C Hdy (log(cs + 1)dT/5) || -
for some absolute constant C independent of cs. Lower bound of (0) wh w= (V.)) can be shown similarly, establishing
(6, wo, w" (V(V) < C Hdy log((es 1)dT/5) |
12

---

Infinite-Horizon Average-Reward RL
Hence,
[[P.V - [PV]((s,))] = 1(pp(s, a), wi(V= (=1))) V (I(s, (V,))
= =(40(8, a). w - w (V.))
SC Hd log((cs 1)dT/6) |
where the last equality uses the fact that wV*) = Is ( (s))) ) is linear. remains to show that there exists a choice of absolute constant cg such that
C Colllee + 1) + ( /6) I ca cgy/og((T/0).
Noting that (og(dT/)) 2 log 2, this can be done by choosing absolute constant cg that satisfies Colog 2 + log(c3 + egvlog2 2.
Lemma A.6. The clipping operation CLIP(æ; L, U) has the following properties:
(i) CLIP(E; L) CLI((1 c; 1.L-c,0 -L--U -c-
(ii) CLIP(E; L, U) < CLIP(y: L, U) if
(iii) CLIP(2; L, U) < x and only a 2 L.
(iv) CLIP(E; U) 2 CLIP(1; L' U²) if 2 L' and U 2 U².
Proof. The proofs straight from the definition.
B. Deviation-Controlled Value Iteration
B.1. Positive Result for Tabular MDPs
In this section, we show that the scheme used in the algorithm y-LSCVI-UCB+ for controlling the deviation between chains of value functions with different clipping thresholds not necessary the tabular setting.
To reuse the notations developed for the linear setting, we treat the tabular setting with the size of the state space S and the size of the action space A as the SA-dimensional linear MDP setting where each pair (s, a) E S x A is mapped to one-hot encoded vector (p(s, a) (ss.a) E SAA where the entry associated to (s,a) is equal to and all other entries O. We show that under the tabular setting, Algorithm that removes the step for clipping Q from 7-LSCVI-UCB+ successfully control the deviation of a chain of value functions from its previous chain. Note that the algorithm uses the doubling-trick that updates the covariance matrix used for regression only when its determinant doubles. The trick is used to facilitate the analysis of the difference Q (s, a) - Ø (s, a) shown in the proof of the lemma below.
We À 0 and treat A, as the pseudoinverse of A, and set [] a)llA, + when ||<p(s, aolsaa)lll, that is, when the direction cp(s, a) never explored. Then, as shown in the following lemma, the deviation between chains of value iterations controlled even without the extra scheme used for the linear MDP setting.
Lemma B.I. When rumning 7-L-CIIUU--SS algorithm without deviation control under the tabular setting, for all L E [T].
u E [t: TJ. we have
| (s) v((s)] m. m++1
| (s) - V.(()] S m. - m++1
for all & E S.
Proof. We introduce the notation N((s, 1t s,a, a} and Ni(s,a,s') Σー 1ls, 8, ar a, 8r+1 s'), which is the visitation counts up to (excluding) time step t of the state-action pair (s, a) and state-action-str triplet (s,a,8') respectively. Note that in the tabular setting, we have [P.V](s,a) =
13

---

Infinite-Horizon Average-Reward RL
Algorithm 7-LSCVI-UCB+ without Deviation Control
Input: Discounting factor E [0, 1). regularization constant À > O, span > 0, bonus factor / > 0. Initialize: k+ 1, lx f 1, A1 f AI, m1 + 1-5
Receive state 81-
2: for 1,..,, do
3: (++ x 1
4: for u T, -1..- /d
5: Qt(:)))) + (1(..) + M(P v (ill(())+ B11p(: I-g.
6:
Vi()) c max, a)))
7:
(V()) t
mi + H).
8:
end for
9: Take action at + argmax Qi(s,, a). Receive reward r(st, at). Receive next state $-41-
10: A++1 t A + (p(s,, ae)sp(s),
m++1 f- (/4111)41)
my
2eet < (et(A then
13:
k k + 1, to + ++1.
14:
end if
15:
end for
(MM. (VV( which is the expectation of V with respect the empirical transition prob-
ability kernel P:: () Ni(s, s¹) /NN(ss a). Hence, Pe is linear such that [P.Vi](s, a) [P.va](s, (V1 V2)](s, a), and satisfies (s,a) & | for any function A S + R. We exploit these facts prove the lemma.
We show by induction on = T 1, ..... 1. Fix f such that both t and + are in the same episode k. For the base case = T + 1, we have p+++ I+1 (s) V7 (s) = - for all E S, and trivially, we have |V (s) - V (s)) I my m++1-
Now, suppose [s)
(8) - Vi (+)] S m, - m4+1 for all E for some u E [T]. Then,
14t (s, a) 1 (s. a)l s ([Pr, V ((s,a) [Pr, Vitllss, a)) S m, m
where the first inequality by the fact that (. ^ - is a contraction and the second inequality is by the previous discussion on P.py being a expectation with respect to proper probability kernel in the tabular setting. Since max. Q(:, a) is a contraction, it follows that (s) Ve+1 (s)l < m, m Hence, using the fact that m, 2 m4+1, we have
(i()s) V CLIP (V: mc, m, + H) CLIP( (s); me+1. m441 + H) CI.IP(V (8)
m++1; my, + H) CL.I (8); (s); m41 H)
CLIP(V CLLI (s); m441, + H) + m, - m - CLIP ( m1+1, m41 + H)
m m++1
where the second equality uses the property (i) of the clipping operation. Similarly, we have
(i((s) - (s)+ = CLIP(( (s): m. m, + H) - (LIP(Vtt((s): m,4 + H)
2 (V. m4; my H) CI.IP(Zt+1 (s); m H)
2 CLIP(V mr m, + H) CLIP(( my + m441 me, mc + H)
CLIP(V (s): m. m, H) CLIP(VA) (s): m4+1. m4+1 H) mm m
m m4+1
where the second equality uses the property (i) of the clipping operation. The two inequalities establish [V( V=++(ss) my m4+1 desired. By induction, the proof is complete.
14

---

Infinite-Horizon Average-Reward RL
B.2. Negative Result for Linear MDPs
Proof of Lemma 3.1. For convenience, let n 2m. is odd, we can take Φn 0 and similar argument holds. Take
Φ1 ...... 6m (n) 1/2, 0, ..... 0) and 9m+1,..... 2mm (n: - 11 O. ..... 0) where 7) 0 is to be chosen later. Take 91 y2m A and À = 1. Then, A, d n 4, 0, ................................ 0) + and Σ 3: (nAn, .......) 0). Hence,
Wn ( O, ...,, 0). follows that, choosing &b (1, ................................ 0), get nAn
((w,, Φ)
Tj +
Choosing 1/ Vn. we get (w,,, x) 1AVn, which completes the proof.
B.3. Deviation-Contrrolee Value Iteration for Linear MDPs
Lemma B.2. For all t [T]. E [t: T), we have
(++t(s) Vi(()] S m4-1 11411
- -1++1 IV+ (8) Vi((s) S -m-1--1
for all S.
Proof. We first show that V (s) (s) 2 m4-1 m4+1 and (s) Vi((s) -m4-1 m141. By definitions of Q and Qh we have
2 a) (s (s,a),
(s,
= (Q%(s,)) - mm + m4+1) V m + m4+1)
2 (8, m + m4+1
and
(1 a) = (.)
(s,
t (s, A 1t- (s,aa
5 o (s,a). (
Chaining the two inequalities, we get Q (s, a) 2 (s, a) - 11--1 + m141. It follows that
Ft+1 (s) = max Q (s,aa)
> max (s, (5 a) 11:-1 m4+1
= (i()) - m + m4+1
which shows the first claim. Hence,
V2+1 CLIP 2 (8); m4 1441 + H)
2 CLIP (1()) m4-1 + M M441 M4+1 + H)
CLIP(V m4-1; 14-1 H) m4-1 + m441
2 CL) m) m. + H) m:-1 + m2+1
(s()) m,-1 + m4+1
where the second equality is by Property (i) of the clipping operation and the second inequality is by Property (iv) of the clipping operation and the fact that m m. This shows the second claim.
15

---

Infinite-Horizon Average-Reward RL
Now, show that (s) Vi( S m - m441 Qu we have
and ((+1(s) Vi((s) S m m4+1- By definitions of Q and
2 = CLIP((tt a); (..
S (stt(ssa)
= (5(,a) 21
and
(s,
a))
10.0(1,00 - m + m V (s, m + mc+1)
(s,a) m + m++1
( 14-1 1 + me+1.
Chaining the two inequalities, get Q (s, a) S ( a) + m m4+1, and it follows that
Ç max Qu e++1 (s.a)
S max Q7 a) + m m4+1
(s) + m4-1 m4+1,
which shows the first claim, Hence,
V (8) CLIP(VV ms), + H)
CLIP(V((s)) + m, m4418 M4+1 H)
S CLIP((.((s) + m. - m4+1; me, my + H)
(s) m4+1 m,+1 H) m. m++1
S <CLIP(V((ss::)) m,, my + H) + m, m4+1
(s((s) + m. M4+1
(s) + -m-1 m4+1
C. Regret Analysis
We first prove the optimism result that says the value function estimates are optimistic estimates of the true value function.
C.1. Proof of Lemma 3.4
Proof of Lemma 3.4. We prove under the event & defined in Lemma A.5, which holds with probability at least 1 - 8. We prove by induction on t and u.
Suppose (s) 2 (*),,, (T)) 2 (*()) and (x, 2 Q* a) hold for all 5 1,..., L - and a [r : T) and
(s, E S x A. If we show that (s(s)) 2 (s),,, (s) and @ a) 2 Q* a) for all u E [t T' and (s, a) E S x A,
the proof is complete by induction on t. We show this by induction on u T 1,,,
The base case u + holds since (s) I 2 V*(s) for all & e Now, suppose V (s) 2 V*(s) for all
16

---

Infinite-Horizon Average-Reward RL
E S for some u E [t + 1: T. Then,
1
(u(s,a) ( (((, (1)p(s, 1-7
2 (r(s,a) + + - 1 7
2 (r(s,a) 7 (s. A
1 1-7
Q"(s,aa)
1-
(s)
where the first inequality is by the event &, the second inequality by the induction hypothesis. The second equality is by the Bellman optimality equation. This shows (u a) 2 (s, for all (s,a) E A as desired. Additionally,
())
(((,a)
2 (ur(("((s.))),((..)))...C.C
2 ((ssa)
Q"(ssa)) (Q, (s, (s,
2 (s,
where the second inequality is by the clipping property (ii), and the last inequality holds by induction hypothesis. It follows that
(s()) = max (s a) 2
Note that by induction hypothesis, (s) 2 (*(s) for all t E [t - 1), E [T T) and s E S. Hence, m, min(V, (..V (sx), (s ... V22 2 min(V*(s.)) (*-))),.., (*(22), 1- } 2 min,es V*)).. It follows that
(s()) = (s) m. + H!
2 CLIP(V"(s): m, m + H)
2 CLIP(V" (s): min V V*(8') eEES
min V*((') + H)
JES
2 Vs)))
where the last inequality uses the fact that H 2 sp(e*) chosen such that sp(V*) < H. We have shown that
(+) 2 (s(s) holds for all E S, then (s) 2 (s),). (s) and (s, a) hold for all (s, a) e A. By induction on T, ,,..., 1, it follows that (s) 2 (s). (s) 2 (*(s) and Q (s, (s, hold for all (s, a) S A. The
proof is complete by induction on t.
Now, show upper bound of the action value function estimate, which is direct consequence of the concentration inequality in Lemma A.5.
C.2. Proof of Lemma 3.5
Proof of Lemma 3.5. We prove under the event & defined in Lemma A.5, which holds with probability least 1 8. Fix any E [T] and E [ TJ. By event E, we have
+ (s,, a) + Blpp(1 )1A,;)))) ^ 1- (s) (r(s, + + 1
1
r(s a) + a) + 23)
17

---

Infinite-Horizon Average-Reward RL
for all / [ Hence, by Lemma B.2, have for / 2 4 that
"s, a) I r(s,a) +
S a((,,) ( +,-33 m4-1 + m my
+ 2(m4-3-- -4).
Therefore, for t 2 4, we have
(s, = Cup(C[((s.0)LL.(ss.....
(s,
= - (s,a) (s.o)
S <r( + PVV a) + 23] a))A," + 2(m4-3 m²)
Finally, the following lemma will be used for bounding the sum of the bonus terms.
Lemma C.1 (Lemma 11 in Abbasi- Abbasi-Yadkori et al. (2011)). Ler (Φ1112 be bounded sequence in F with 1| S 1 for all 2 1. Let Ag and A, = Σ Φ + I
Then,
Σ of A 0: 2 det(Ar) & 2d log(1 + t).
C.3. Proof of Main Theorem
Now, we are ready prove the main theorem.
Proof of Theorem 3.6. We prove under the event defined in Lemma A.5, which occurs with probability least 5. By Lemma 3.5, we have for t 2 4,
(s S a( 71PV442l(ss 28]1 a)),," + 2(m 3 -me).
Plugging in и t 1, t- St, t- ae, we get
RT [v r(st,a)))
Σ (J (1(s), + ((s,)) 200 + 2(m;-3 - 0(1)
Σ (J - (1 -- (841))
Σ (844)) -Q((st
(a)
(6)
T
15p(5, aoll, +0 1
(PV4
( +2
1=1
(d)
Bounding (a) By the optimism result (Lemma 3.4), we have Vi((s) > (s) for all E [T'] and E [t 7] with high
probability. It follows that
J -1-1-7) S J-" (1- ( {1--)ssp(²")
where the last inequality is by the bound on the error of approximating the average-reward setting by the discounted setting provided in Lemma 2.3. Hence, the term (a) can bounded by T(1 - >))p(u*).
18

---

Infinite-Horizon Average-Reward RL
Bounding (b) Using Lemma 3.2 that controls the difference between V and Vi we have
V (8c+1) = CLIP(V 1 (9++1); me, my + H)
(LIP(Vi+4 (9++1) - my + m4415 Mi--1 Mx41 H) + my m++1
I CLIP(V/4 m m441 + H) + my M4+1
Vet (8t+1) + m M4+1
Vi+1 V (s++1) 200-11 2m1+11
where the second inequality holds because V (8++1) 2 m4+1 by Line 13. Hence, Term (b) can be bounded by 0 1 using telescoping sums of V++1 E [T] and E TT.
2+1 (8t+1) - (8)) and 2m4-1 - 2m and the fact that V I I-7 and m4 S I- for all
Bounding (c) Since V is F.-maaauaall where F, is history up to time step t, we have (8441) [PV/il($s az). making the summation (c) summation of martingale difference sequence. Since sP((+1) I H ((sp(u"))TToo((() (Tlog(1/)) using Azuma-Hoeffding inequality.
for all E [ the summation can be bounded by ((sp(v))
Bounding (d) The sum of the bonus terms be bounded by
1/2
3
1pp(s) S BVT
Σ 11 a)))
S (OB8/TTlog
where the first inequality is by Cauchy-Schwartz Schwartz and the last inequality is by Lemma C.I. Combining the four bounds, and choosing Lemma 3.3, get
sp(u*) and choosing $ (o specified in
Rr O(T(1 - ~>)sp("") + T sp(c"))/Too((11))) Toog(1/0) (T log T)
Choosing such that 1 1-y VT, we get
Pr S
log T))
D. Covering Numbers
In this section, we provide results on covering numbers function classes used in this paper. We use the notation (FF ||-II) to denote the e-covering number the function class F with respect to the distance measure induced by the norm || ||.
We first present a classical result that bounds the covering number of Euclidean ball.
Lemma D.1. For any > the d-dimensional Euclidean ball Ba with radius R > 0 has log-covering number upper bounded by
log (BB ||- I12) < dloo(1 + 2R/s).
Using this classical result, bound the covering number of the function class that captures the functions Q' (.. encountered by our algorithm.
Lemma D.2 (Adaptation of Lemma D.6 in Jin et al. (2020)). Let Q be class of functions mapping from S x A to RR with the following parametric form
Q(: (w (IoT(p(;)))) (p((s))) + pp, 3 -
(2)
19

---

Infinite-Horizon Average-Reward RL
where the parameters (w, 8, v, A) satisfy |||||| S L, B [0, and [0, D), and A is a positive definite matrix with minimum eigenvalue satisfying Amin (A) À 0. The constant M > is fixed. Assume [|(p(s, a)]l - 1 for all (s, a) pairs.
Then
log.N((Q.11 1loo) - dlog(1 1 + 8L/s) + log(1 8D/E) + dl log/1 + /d2/2 B²/ (A=2))
Proof. Introducing A = =/AA11, we can reparameterize as
2(:)) = (wTT(w:)))
(p(:,)))) + / Aup(: (pp(s))))p((())))))))))))))))))) A
U UE [0, DJ. For any pair of functions Q1, Q2 E Q with where the parameters (w, v, A) satisfy ||w|2 < L, ||||| < B²X-1, parameterization (Wi, U1, A1) and (W2, 22 A2), respectively, using the fact that A M is a contraction, we get
|Q: Q21lx I sup [w)] (p a) + + (s) Al4(s, - (w2 sp(s,, a) + 02 + VD(s,a) (p((s.))AAsp(ss.)))
8,0
[(w] T Φ + + vΦ Δ1σ) (w) Φ + + v $ A2T)2
sup I11|||1-S1
sup
[(w] w2)² Φ + |0 02
sup V VIOT (Ai A2)Øl
||w]
w> + |1 U2 + IAI A 12
< W1 wy + |1 22ن + VIA41 A2l1F
where the third inequality uses the fact that | V S x y| holds for any 2, 2 0ndd ||| || denotes the Frobenius norm.
Let C. be an e/4-cover of {un E Rd: ||w||| S L.} with respect to the 1.2-norm, CA an 8² /4-cover of (A E TRdxd || S d2/2 B² with respect to the Frobenius norm, and C, an e/2-cover of the interval [0, D). Then, treating the matrix A E Rddd as long vector of dimension d x d, and applying Lemma D.I, we know that we can find such covers with
log (Cwl I dllog(1 + 8L/E),
log|Cal S d² log(1 + (dd ((E?)),
log/C.1 S log(1 + 8D/E).
Hence, the set of functions
Co (Q RRERRSAA :SAA w ((()(..)) + + v /vp(..)7 AAp()))) w E Cw., A CA.
has cardinality bounded by log [Col S d logg(1 8L/s) d2 log(1 8d B² ({E=)) + log(1 + 8D/e). We can show that Co defined above is an e-cover for Q as follows. Fix any Q E Q parameterized by (w, v, A) and consider Q E Q parameterized by (w, U, A) where き C. with || 1 e/4, T C. with |0 ह| S e/4 and Ā E CA with ||A Á F S ///4. Then, by the bound (3), we have IQQ loe S e as desired. This concludes the proof.
Lemma D.3. Let V be class of functions mupping from S to defined as
V {max a(- Q(--)) = CLIP(QI(..)))) Q2(-)) ((.()))) Qu...., 2}
where the function class Q is defined in Lemma D.2. Then,
log No (V, [|x)) S 5d log(1 + 8L/e) + 5 log(1 + 8D/s) + 5dd log/1 + 8/ (AE2))
Proof. Let W be a class of functions mapping from S x A + R of the form
Q(:-)) (L::(Q((::::2<<))) v Qs(. Qa(.))))))))))). Q)(,.))
where Qi,...,
......,, Qs E Q Let Co be an e-cover of the function class Q with size log /Col S d doogg11 + 8L/8) + +log(1 +
4D/E) + log[1 + (22/33/((x=)) Such a cover exists by Lemma D.2. Let C be defined as
C = {Q E SXA, Q(: ( Qa(:)) (..,)))).4()))) Qs(:)),
Co).
20

---

Infinite-Horizon Average-Reward RL
Algorithm 4 7-LSCVI-UCB (flawed initial version in arXiv by Hong et al. (2025))
Input: Discounting factor E [0, 1), regularization constant À > O, span H > 0, bonus factor / > 0. Initialize: + 1, tx + 1, A1 t XI, Q1(,)), V1(+) + 1- for E [T].
1: Receive state 81-
2: for time step t 1, ..... do
3: Take action a, argmax, c( (s, a); Receive reward r(se, az); Receive next state $141-
4: A, t A-1 + ( at) (s) a.)
5:
Q++1(;-) (((,)) + 7 (1 Vil( + Bl1g(: (11x+()))))1 r
6:
(-+(()) + max, Q4)1.aa).
7:
V--(()
(o)(Ve+1));minn.a V8+1 minves Ve+ (5') + H).
8:
(r < det( then
9: + k + 1, tx + 1.
10: end if
11:
end for
Then, we have log |C| v 5 5lg Col. and we can show that C is E-cover of W follows. Consider function W W, with W(:-) CL:
v Qs(.:))Qu(..)) A Qs(:-)) where QI...., Qs Q. Let Q E Co be the approximation of Q, for = 1,...., 5 such that ||Q; - Qillc I a. Such a Q, exists since Co is an e-cover of Q. Let Then, @ E C and
= (
Q(:-) 0 Q(((.)) cun(@(l.)++<000+))))))(()00 +e), (Q4(.)) + + + (Qb(;)) + +))
= curr@1110044.11aaaa:2::::))1111 +E
(((+))
Similarly, we have
Q(:-)
-., -( -e))
2 (ux (
= [(.-)) -5,
which shows I|Q - @l S e, and that C is an e-cover of W. Since max, is contraction map, it follows that V =
(max, Q(, a): Q W) is covered by V {max, Q(; Q C). The proof is complete by observing that log |-| < log [C] < 5 log |Col. and that there exists E-cover Co for @ with log Col S d + SL/E) + log(1 + 8D/s) +
d2 log[1 8d) /2///22/// /(E=)) by Lemma D.2.
E. More Discussion on Previous Work
In this section, we provide more detailed comparison with prior work. The idea of using value iteration for infinite-horizon average-reward linear MDPs via approximation from the discounted setting was first introduced by Hong et al. (2025). However, the initial arXiv version of their work contained a flaw in the analysis. This issue was later corrected in the published version, which involved significant modifications to the algorithmic structure, resulting from the original version. The corrected algorithm is discussed in Section 2.4 of the main paper. For completeness, we review the original (incorrect) version in this section and explain how Hong et al. (2025) addressed the issue.
substantial departure
The incorrect version is shown in Algorithm 4. Unlike the corrected version (Algorithm 1), which plans for future policies for the remaining time steps by performing backward value iteration to compute action-value functions Q, for the remaining time steps, the flawed version updates the action-value function in place, meaning it performs a value iteration and updates the action-value function directly at each time step, and selects an action based on this updated value function. For a technical reason, the algorithm runs episodes, starting new episode when the covariance A, doubles (Line 8).
21

---

Infinite-Horizon Average-Reward RL
Although simpler and more memory efficient, the in-place action-value update scheme alone appears insufficient, and the incorrect version of the paper introduces a max-pooling step (Line 3) that pools Q-functions such that the pooled Q function Qt m is monotonically increasing within the episode k. To motivate this modification, consider what happens if the action a, is directly taken with respect to the value function Q1, without applying max max-pooling. Note that by uniform concentration bound on P. V, we have
Qr+1(s, S r)(,, +7 23]ly(ss, a)]la,
(4)
for all 7 [T], s E S and E A. Using the incquality with +- t + 2, St, f- ae. bound the regret as:
T
Rr
Σ (J" - r(s).
Σ (J" -Q+2(((, (PV[444(((s)))) + a
t=1
T
-1- (1-2))++(((444)) Σ (411)) Q(+2(s),a))
T
((PPV++il(s),)) a.) - V141(0441)) 23 (e)ll;,
Σ
Here, the in-place nature of value iteration causes misalignment in the second: the Q-function in the second part of the term is one iteration ahead of the Q-function in the first part. This mismatch complicates the regret analysis and undermines the telescoping cancellation typically leveraged such proofs.
One potential remedy is to enforce monotonicity in the Q-function within an episode by adding line Q++1 < Q: V Q++1 after Line 5. With such modification, telescoping goes through. However, this approach introduces a complication: as the funnctionn becomes increasingly complex with each update, the covering number of the function class containing all such Q- functions grows exponentially with T. As result, the uniform concentration bound for P.V becomes vacuous.
To sidestep the covering issue, the initial (incorrect) version of Hong et al. (2025) does not enforce monotonicity in Qt. maintaining Qt in a function class with low covering number. Instead, it max-pools the Q-functions as Q: ma Q- a) and selects a greedy action a, with respect to the pooled function Q.- The idea is to make Q. monotonically increasing in without running into covering issue. Denoting by 71 a) = argmax(e(nen)) Qr a) for in episode k; and using the inequality (4) with 7 + Tr(s, a) - 1, 8 t- 8t, a t- ax, and using Qr.(s. (Sc, ax) = Qe(sr, at). we get
RT S
Σ (J' (n( + + PPV (x. a.) 23]lyp(s,, ai)l,,
T
T
Σ (J* - - (1->) (
Σ
(V - Qe(se, ar))
T (s) - ((+1(+++1) + 2,3
T
Σ
||((s)
t=1
The incorrect version of Hong et al. (2025) bounds the second term as follows (we slightly adapt their argument for clarity).
V (((-))
S V V=(()
= max Q Q1 (8)+1,,
S max max Q-(4++1:)) rE]te:t-1]
max ((+1())41,
((+1)
22

---

Infinite-Horizon Average-Reward RL
which allows for telescoping sum. However, the second inequality above is wrong. Although re(s,, at) E 14x : 4J. (8(8; ae) 1 is not in the interval [4x t when (s1, dz) 4g- Due this off-by-one emror in their analysis, the regret bound fails.
The corrected version fixes the issue by completely restructuring the algorithm. Specifically, it uses a backward value iteration scheme, so that the value function Q++1 used for selecting an action 6++1 at time t + is one value iteration behind Qt. With this scheme, the time index in (4) changes to:
Q+ a) S r(s,a) + ((s + 23]ly((s, 2
and the regret bound for the corrected algorithm becomes
E(-- - r(s,, a1)) E(r Qe(ss, a1) + + + +2 +2 a)ll,,
(J (1 (1-2)Vot(44411) + E(Oet((ee)) Qi (8t,
[(PVi az) - V(+1(Se+1)) + 23 Σ ||5( ai)(aa,
Notice the change the time index the second term. Without the need for further modification of the algorithm, the second term can be bounded using telescoping sum, done in Appendix C.3.
23


Reviews:
[{"review_id": "CfQq4ZiQBt", "reviewer": "Reviewer_CyKa", "summary": "In this paper, the authors have studied the reinforcement learning algorithm for linear MDPs in an infinite-horizon average-reward setting. Previous works approximate the average reward by the discounted one and employ a clipping-based value iteration method. However, it requires the computation of minimum of the value function over the state space. This may be computationally prohibitive. Towards that, in this paper, an efficient clipping technique is introduced for value iteration algorithm. This requires computation of minimum value function over states visited by the algorithm. It has been established that the proposed scheme demonstrates the same regret bound as that of the previous work with a substantial drop in computational complexity which is independent of the size of the state space.\n## update after rebuttal\nThe response addresses my major concerns. I have raised my score to 3.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your time for the detailed review. Your feedback will help us in improving our paper. Here are our responses to your questions.\n\n**Q1: Computational issue \\& Simulation**. You are correct to note that, in the large state space regime, the number of unique states visited over $T$ time steps can be very large, potentially with no repeats. However, our algorithm’s computational complexity does not scale with the size of the entire state space, since we do not enumerate all states. Instead, in the worst case, where states never repeat, the complexity scales with $T$.\nRegarding simulation, due to the theoretical nature of the linear MDP assumption, designing a concrete simulation environment is challenging and, to our knowledge, no simulation has been performed in the linear MDP setting in the literature. we agree that providing a simple simulation would be valuable to the community, and we will aim to include a simulation under a *restricted* linear MDP setting described in our response to Reviewer w193.\n\n**Q2: Why assume reward to be bounded**. Your intuition that the assumption can be removed is correct. And in fact, it is this intuition that It is standard in the literature to assume $r \\in [0, 1]$ without loss of generality. When the actual reward lines in $[0, B]$, say, then we can scale it to $\\widetilde{r} \\in [0, 1]$, analyze the regret bound under the new reward, and then multiply the final regret bound by $B$ to account for the scaling. To avoid carrying the constant $B$ around in our derivations, we assumed $r \\in [0, 1]$. We will add a clarifying note on this point in our final version of the paper.\n\n**Q3, Q5: Assumption on the knowledge of span**. Thank you for bringing this up. Indeed, requiring prior knowledge of $\\text{sp}(v^\\ast)$ is a limitation of our approach. Whether sample-efficient learning is possible without knowing the span in advance has been an open question for a long time, and many existing works rely on this assumption. A recent result by Boone et al. [1] shows for the first time that it can be avoided in the tabular setting. However, extending their technique to the linear MDP setting is non-trivial and will likely require a major breakthrough. We leave this to future work. We will add a remark on this assumption and cite [1] in the final version of the paper.\n\n**Q4: Covering number**. Thank you for the suggestion. In the paragraph following Lemma 3.3, we will describe the general covering argument that uses epslion-net for covering the function class for getting uniform concentration bound and briefly describe $\\epsilon$-covering number of a function class and how the log covering number scales the concentration bound.\n\n**Q6: Setting discounting factor**. The original problem the designer is trying to solve is the average-reward setting. We are proposing to approximate the average-reward setting by a discounted setting with a particular discounting factor. The designer will work with the discounted setting with discounting factor set to the proposed value. So, it is in the hand of the designer to set the discounting factor. We will make it clear in the beginning of Section 3 that the discounting factor is set by the designer to approximate the average-reward setting.\n\n**Q7: Size of the state space and the dimension**. Thank you for the question. When we say \"size of the state space\", we mean the number of the states in the state space. In the tabular setting, we do not assume any structure in the MDP that allows generalizing to unseen states, and the computational and statistical complexity both scale with the number of states. However, in the linear MDP setting, we assume a structure in the MDP that allows for the generalization through the feature mapping $\\varphi$ that maps state-action pairs to a $d$-dimensional feature vector. Due to the feature representation, conceptually, we no longer need to learn about all the states individually. Rather, we only need to learn about $d$ \"directions\", which allows for computational and statistical efficiency. Specifically, the computational complexity and the regret bound scales with $d$, not the size of the state space. With this intuition, we can see that if $d$ is large, then there is more \"directions\" to explore, making both computational complexity and regret large. We will add a summary of this discussion when defining the linear MDP setting in Section 2.3.\n\n---\n\n[1] Achieving Tractable Minimax Optimal Regret in Average Reward MDPs. NeurIPS 2024.", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "Yes", "theoretical_claims": "I have checked the proof , but not in great detail.", "experimental_designs_or_analyses": "Experimental results are absent in the paper.", "relation_to_broader_scientific_literature": "In this paper, the authors have studied the reinforcement learning algorithm for linear MDPs in an infinite-horizon average-reward setting. It has been established that the proposed scheme demonstrates the same regret bound as that of the previous work with a substantial drop in computational complexity which is independent of the size of the state space.", "essential_references_not_discussed": "No", "other_strengths_and_weaknesses": "The paper is well-written and contains some interesting ideas. The problem considered by the authors are relevant and interesting. However, the solution is based on some strong assumptions such as knowledge of $sp(v^*)$. Some results need clarification and lacks intuition.", "other_comments_or_suggestions": "Not applicable.", "questions_for_authors": "My comments are as follows:\n1.\tWhat if the underlying Markov chain is irreducible under various policies? In the worst case, the algorithm can still visit all the states and hence, the computational burden may still be high. I expected some simulations too in this direction to verify the efficiency of the proposed scheme. \n2.\tWhy do we need to assume that $r\\in[0,1]$? I guess removing this assumption also does not create any problem. \n3.\tIt is assume that $sp(v^*)$ is known the learner. The authors stated that this assumption can be relaxed to the knowledge of an upper bound on $sp(v^*)$. However, in this case regret will scale with the upper bound. Knowledge of $sp(v^*)$ or an upper bound on it can both be difficult to obtain. Also, choice of a loose upper bound can result in poor regret. Is there a way in which such a requirement of knowledge can be avoided completely?\n4.\tPlease describe what do you mean by covering number. \n5.\tLemma 3.4 holds when $H\\ge 2sp(v^*)$. How do one guarantee that?\n6.\tIn Theorem 3.6, we need choose $\\gamma=1-\\sqrt{1/T}$. However, typically $\\gamma$ is not in designer’s hand. This makes the algorithm depart from reality.\n7.\tIt is stated that the computational complexity is independent of the size of the states space. However, $d$ is related to the size of the state space. Why is the regret large when $d$ is large? As $d$ becomes close to the size of the state space, regret should be less. Please elaborate", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "rMrcDSpZZ3", "reviewer": "Reviewer_nuyD", "summary": "This paper proposes a computationally efficient algorithm for infinite-horizon average reward linear MDPs. The paper seeks to improve upon the previously proposed approach $\\gamma$-LSVI-UCB by Hong et al'25. The main contribution is that the algorithm proposed in Hong et al.'25 requires to iterate over all the state-space to find the minimum value function for clipping, which might be computationally expensive, especially for linear MDP. Hong et al.'25 assumed some minimum oracle, this paper seeks to improve upon that. The paper proposes a novel idea where one only needs to iterate over the state encountered so far. The paper in particular focuses on bounding the error $V$- $\\tilde{V}$. The paper significantly contributes in this direction.\n\n##Post Rebuttal Update##\n\nAll my concerns have been resolved, and I am happy to accept this paper.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your time for the review and for the suggestion for improving the paper.\n\n**Q1: main technical novelties**. We will integrate the following summary in the introduction section and in Section 3.2 when introducing the method.\n\n1. The main technical novelty lies in designing a clipped value iteration algorithm that ensures each successively generated value function deviates from its predecessor by no more than the difference between their respective clipping thresholds.\n2. We show that a naive adaptation of previous work cannot control this deviation in the linear MDP setting.\n3. A natural workaround would be to clip each newly generated value function with a new threshold so that it deviates from the previously generated value functions by at most the difference in the thresholds. But doing so will make the value functions more and more complex successively, running into an issue when using covering argument for uniform concentration bound.\n4. To address this, we design a novel way for controlling the deviation without running into covering issues. Specifically, we \"pool\" latest value functions in such a way that the difference in successive \"pooled\" value functions is bounded by the the difference in the thresholds. The pooled value function has low complexity so that the function class that captures the pooled value function has low covering number.", "claims_and_evidence": "The proofs of the claims are provided.", "methods_and_evaluation_criteria": "The paper is theoretical in nature.", "theoretical_claims": "The theoretical claims seem to be correct.", "experimental_designs_or_analyses": "N/A.", "relation_to_broader_scientific_literature": "The reviewer does not have any major concern.", "essential_references_not_discussed": "The reviewer does not have any major concern.", "other_strengths_and_weaknesses": "Strengths: \n\n1. The theoretical contributions are significant. \n\n2. The paper is well-written. \n\nWeakness:\n\n1. The algorithm still needs to iterate over all the states encountered, which can be significant for the large time period.\n\n2. Some simulations would be nice to see the difference in terms of computational time and the regret compared to the state-of-the-art approaches.", "other_comments_or_suggestions": "N/A", "questions_for_authors": "1. Can the authors summarize briefly the main technical novelties? in particular, how did they bound the deviation?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "8ciSunIpDx", "reviewer": "Reviewer_w193", "summary": "This paper proposed an algorithm for infinite-horizon average-reward reinforcement learning with linear function approximation. The main problem need to be solved is the computation issue arises from minimize the value function in large state space. To address this, the paper proposed a new clipping technique, and proved that this method achieves the same regret order while enjoy computational efficiency under the large state space setting.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your review. Here is our response.\n\n**Simulation in toy setting**. Thank you for the suggestion for running a simulation in a toy setting. We have confirmed that our algorithm runs in a *tabular setting* (i.e. linear MDP setting with feature vectors orthogonal) with average regret reasonably low when treating the bonus factor beta as a hyperparameter, as is usually done in UCB-type algorithms.\n\nTo our knowledge, no study to date has conducted a simulation under the *linear MDP* setting. Nevertheless, we agree that providing a simple simulation would be valuable to the community, and we will aim to include a simulation. One reason why simulation under linear MDP is absent in the literature is due to the complication of specifying the vector of measures $\\mu$ that ensures $P(s' | s, a) = \\langle \\mathbf\\varphi(s, a), \\mathbf\\mu(s') \\rangle$ is a valid probability measure. However, we believe we can get around the problem by restricting the feature vector $\\varphi(s, a)$ to have L1-norm equal to 1, and each of the $d$ measures in $\\mathbf\\mu$ are probability measures. We will aim to conduct experiments under the *restricted* linear MDP setting.", "claims_and_evidence": "Yes. The paper clearly provided the computational complexity to support that the proposed algorithm runs in polynomial time.", "methods_and_evaluation_criteria": "Yes.", "theoretical_claims": "I checked the proof in the main paper and appendix A, and do not find any issues.", "experimental_designs_or_analyses": "N/A", "relation_to_broader_scientific_literature": "N/A", "essential_references_not_discussed": "N/A", "other_strengths_and_weaknesses": "Strength: The explanation of the motivation and idea of why and how to do clipping is clear and easy to understand.\n\nWeakness: The work lack some (at least) toy example to illustrate the effectiveness of the proposed algorithm.", "other_comments_or_suggestions": "N/A", "questions_for_authors": "N/A", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "QHG1kEYKx7", "reviewer": "Reviewer_3Auz", "summary": "This paper tackles the open problem of proving a rate optimal regret bound in average reward infinite horizon linear mdp with a computationally efficient algorithm. The problem it is solved successfully, using a double loop structure inspired by hong et al. 2025 and a deviation controlled mechanism to make sure that the iterates produced by least square value iteration with different clipping thresholds could be bound by the difference of the clipping thresholds.\n\n### After rebuttal\n\n My opinion remains positive. The assumption on bounded features and weights is clear now but I think it would be better if the authors make clear that finding features with the desired boundness properties requires computing a MVEE.\n\nPlease make sure to add the comparison with the failed attempt in Hong et al. 2025v1. I think this is very important for the placement of the paper in the literature.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you very much for your thorough review and suggestions for improving the paper. Here are our responses.\n\n**Minor error in proof**. Thank you very much for catching this. We will replace $m_{t + 1}$ with $m_t$ for the equality to hold.\n\n**Relation to previous work**. Thank you for the suggestion. We fully agree that detailed comparison with Hong 2025 v1 will benefit the community. A short explanation is that Hong 2025v1 that uses \"max-pooling\" of Q functions, which had an error, happened to allow computationally efficient clipping without additional algorithmic modification. Hong 2025v2, which fixes the error using double loop structure could no longer use the computational efficient clipping. Our submission introduces an algorithmic modification that allows for computationally efficient clipping under the double loop structure. We will mention the attempt made by Hong 2025v1 in Section 2.4, and add detailed comparison in the Appendix.\n\n**Knowledge of T, H**. We will make it clear to the reader that $T$ is required by adding $T$ in the list of input parameters in the algorithm box, and mentioning it in the analysis when we set $\\gamma = 1 - 1 / \\sqrt{T}$. We will add a remark following the Theorem statement that using *doubling-trick*, we can get away with the knowledge of $T$ at the cost of incurring additional factor of $\\sqrt{\\log T}$ in the regret. As for the knowledge of $H$, we will remind the reader after the Optimism lemma (Lemma 3.4) and after the main theorem statement that knowledge of an upper bound of span is required. As mentioned in our response to Reviewer CyKa, we will also mention that there is a recent work that relaxes this assumption for the tabular setting, and that we leave relaxing this assumption to future work.\n\n**Discussion on Bellman optimality equation**. Thank you for the suggestion. We will add discussion on the relation to Communicating/Weakly Communicating MDPs and Ergodic assumption. Bellman optimality equation assumption is strictly weaker than Communicating/Weakly Communicating MDP which is strictly weaker than ergodic assumption. We will mention this fact with brief reasoning and citation.\n\n**On boundedness of reward vector**. \nNote that the paper by Wei et al. 2021 \"Learning infinite-horizon average-reward mdps with linear function approximation.\" discusses this in detail in Appendix A. (Based on your comment, we think you were referring to Wei et al. 2020. \"Model-free reinforcement learning in infinite-horizon average-reward markov decision processes\"). Their reasoning is as follows. Given any feature mapping $\\phi$ with $\\Vert \\phi(\\cdot, \\cdot) \\Vert_2 \\leq 1$ and a reward function in the form $r(\\cdot, \\cdot) = \\phi(\\cdot, \\cdot)^\\top \\theta$ such that $\\vert r(\\cdot, \\cdot) \\vert \\leq 1$, there always exists an invertible matrix $A \\in \\mathbb{R}^{d \\times d}$ such that $\\Vert A \\phi(\\cdot, \\cdot) \\Vert_2 \\leq 1$ and $\\Vert A^{-1} \\theta \\Vert_2 \\leq \\sqrt{d}$, which enables us to work with $\\widetilde\\phi = A \\phi$ and $\\widetilde\\theta = A^{-1} \\theta$ instead that satisfy $\\Vert \\widetilde\\phi \\Vert_2 \\leq 1$ and $\\Vert \\widetilde\\theta \\Vert_2 \\leq \\sqrt{d}$. They argue in their proof that such a transformation $A$ is the transformation that transforms the MVEE of the feature mappings into a unit ball. When citing their work, we will add which section of their paper to refer to (Appendix A), and briefly explain their argument.", "claims_and_evidence": "Claims are convincing", "methods_and_evaluation_criteria": "Rigorous proofs.", "theoretical_claims": "I checked the correctness of all the theoretical statements.\nI found just a minor error at the end of page 15 in the equation at line 820 $m_{t+1}$ should be replaced with $m_t$, otherwise the authors \ncould not conclude that the first ferm equals $V^t_u(s)$.", "experimental_designs_or_analyses": "see above", "relation_to_broader_scientific_literature": "Yes, related to the previous attempt towards solving this problem.\nThis is quite well done but I have a request for the author. please find it below.\n\nTo my knowledge, there was a previous attempt in the first version of the paper uploaded in arxiv that claimed to achieve the same results \nbut without the double loop structure and therefore with a better time complexity.\nUnfortunately, the authors of Hong et al. 2025 claimed in their v2 that the previous result contains a mistake.\n\nI think that the mistake in Hong et al 2025 is in the maximum over the past Q functions, this algorithmic  technique makes the covering number of the state value functions space to be exponential in $T$. This is indeed avoided by the current submission that\nreplaces the maximum over past value functions with the double loop structure.\n\nIn my opinion, it would be helpful for the community if in the current submission, you could add a paragraph explaining the differences with Hong et al. 2025 v1 and in particular explaining why the current approach fixes the issue with the previous approach.", "essential_references_not_discussed": "None", "other_strengths_and_weaknesses": "Well written paper", "other_comments_or_suggestions": "Make clear that Algorithm 1 and 2 need to know both $T$ and $H$, especially it seems very difficult to obtain an algorithm that works without knowing the value of $T$ in advance given the double loop structure.\nThe author should make this limitation clearer.", "questions_for_authors": "How does the Bellman optimality equation in Assumption A relates to structural assumptions often imposed in Average Reward infinite horizon problems such as Communicating/Weakly Communicating MDPs ? I think this should be discussed better in the manuscript before stating Assumption A.\n\nWhy in Assumption B is reasonable to assume that the reward weights are bounded by $\\sqrt{d}$. I think that in case of very badly conditioned features the reward weights might need to be larger than $\\sqrt{d}$ to realize the reward function.\nLet imagine to have two features $[0,1]$ and $[\\epsilon, 1-\\epsilon]$, now to write the reward function $r=[1,0]$ the weight norm should be as large as $1/\\epsilon$. However, $\\epsilon$ can be made arbitrary small so the quantity $1/\\epsilon$ can become arbitrary larger that $\\sqrt{2}$.\n\nMoreover, the authors say that these assumptions are without loss of generality and refer to Wei at al. 2021 to see why this is the case.\n\nUnfortunately Wei et al 2021 is only for the tabular setting so it does not contain information about this assumption that involves linear MDPs.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: The paper studies reinforcement learning in infinite-horizon average-reward settings with linear MDPs. Comparing to the prior work, this work's algorithm relaxes the condition and only requires the algorithm to know the minimum of the value functions over the set of the states visited by the algorithm instead of the entire state space. Thus the work improves prior work in terms of computation complexity. 

Reviewers in general are positive about the paper and the authors rebutal also successfully addressed some of the concerns from the reviewers. 

I think some suggestions from the reviewers are indeed very good and can make the paper stronger. Please make sure to include the following discussions in the paper: (1) discussion about the comparison to the previous work from Hong et al. 2025v1, and discuss the issues related to the covering number and how the techiniques in this paper handles this issue; (2) discuss how to ensure the boundness assumptions using MVEE and the computation cost from MVEE. I think adding these discussions would make the paper more complete.
Decision: Accept (poster)