Pith. sign in

REVIEW 26 references

A Computationally Efficient Algorithm for Infinite-Horizon Average-Reward Linear MDPs

T0 review · reviewed 2026-08-16 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read A discounted value-iteration algorithm with visited-state clipping and deviation-controlled updates achieves ~O(sp(v*) sqrt(d^3 T)) regret for infinite-horizon average-reward linear MDPs with computational cost independent of the state-space size.

arxiv 2504.11997 v1 pith:YZOYZIQJ submitted 2025-04-16 cs.LG cs.AI

Kihyuk Hong , Ambuj Tewari This is my paper · ORCID
classification cs.LGcs.AI
keywords valuealgorithmaverage-rewardclippingefficientlinearsettingspace
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

In an infinite-horizon average-reward reinforcement learning problem, the agent keeps acting forever and wants to maximize the long-run average reward. In a linear MDP, the transition and reward are assumed to be linear in a known feature vector, so the state space can be very large or infinite. A previous algorithm from the same group, gamma-LSCVI-UCB, achieves a statistically near-optimal regret rate but its clipping step needs the minimum of a value function over every state in the state space. That is impractical when the state space is large or infinite.

The new algorithm, gamma-DC-LSCVI-UCB, keeps the same idea but clips value functions using only the states the agent has actually visited. It maintains a decreasing clipping threshold m_t. Because the next state is not known when the threshold is set, clipping can overshoot the value at the next state. The paper introduces a deviation-controlled value iteration step that clips the Q-function between bounds built from the previous two value-function chains, which makes the error telescope over time. This lets the regret analysis go through with only visited states.

The main theorem states that with the discount factor set close to 1, the regret is ~O(sp(v*) sqrt(d^3 T)), matching the best previous bound, and the computational cost is O(T^3 d^2 A), independent of the number of states. The proof is entirely analytical, with no experiments. There are some presentation issues: the theorem text references Algorithm 1 instead of the new Algorithm 2, and the covering-number lemma does not explicitly cover the shifted clipping bounds used in the algorithm. These appear fixable but should be corrected.

Extended reading notes

Core claim

Theorem 7 states: under Assumptions A and B, running the algorithm with gamma = 1 - 1/sqrt(T), lambda = 1, H = 2*sp(v*), and beta = O(sp(v*) d sqrt(log(dT/delta))) guarantees with probability at least 1 - delta that regret is at most ~O(sp(v*) sqrt(d^3 T) log(dT/delta) log T). If the paper is correct, the proposed algorithm achieves this order-optimal regret with computational complexity O(T^3 d^2 A), independent of the state-space size. A caveat: the theorem says Algorithm 1, but the new method is Algorithm 2, so the text appears to contain a typo.

Load-bearing premise

The uniform high-probability event used in Lemma 4 and Lemma 12 requires a covering-number bound on the function class generated by the algorithm's Q updates. As written, Lemma 19 covers only functions CLIP(Q1; Q2 v Q3, Q4 ^ Q5) with Qi in a fixed parametric class Q, but Algorithm 2 uses lower bounds L_t^u = (~Q^{t-1}_u - m_{t-1} + m_t) v (~Q^{t-2}_u - m_{t-2} + m_t), i.e., Q functions shifted by threshold differences. Those shifted functions are not in Q, so the covering bound is not established for the actual algorithm. If this cannot be repaired, the concentration bound, and with it the regret theorem, would fail. Location: Lemma 19 in Appendix D applied to Algorithm 2, Section 3.1, Lines 6-8.

Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Assumptions & free parameters 0 free parameters · 6 assumptions · 0 invented entities

The central claim rests on the standard average-reward structural assumptions (Bellman optimality, bounded span, linear MDP) plus concentration and covering machinery from prior literature. No hidden fitted parameters or invented entities are introduced. The main fragile point is that the covering lemma for the new algorithm's function class is not stated for the shifted clipping bounds.

assumptions (6)
  • domain assumption Assumption A: there exist J* and bias functions q*, v* with J* + q*(s,a) = r(s,a) + [P v*](s,a) and v*(s) = max_a q*(s,a).
    Standard Bellman optimality equation for weakly communicating average-reward MDPs; it makes the optimal gain independent of start state and is used throughout the regret analysis (Section 2.1).
  • domain assumption Assumption B: transition and reward are linear in a known feature map phi, with r(s,a) = <phi(s,a), theta> and P(s'|s,a) = <phi(s,a), mu(s')>.
    Defines the linear MDP setting (Section 2.3); needed for regression-based estimation of [P V].
  • domain assumption Boundedness conditions (1): ||phi(s,a)|| <= 1, ||theta|| <= sqrt(d), ||mu(S)|| <= sqrt(d).
    Stated as WLOG for the linear MDP setting; supports norm bounds used in Lemma 10 and the concentration arguments.
  • domain assumption The learner knows sp(v*) or an upper bound on it; the algorithm sets H = 2*sp(v*) and beta = O(sp(v*) d sqrt(log(...))).
    Section 2.1 states the span is assumed known; if only an upper bound is known, the regret scales with that bound. This is an input to the algorithm, not a fitted parameter.
  • domain assumption The action set A is finite and the reward r(s,a) lies in [0,1].
    Defines the interaction protocol in Section 2.1; the size of A appears in the stated computational complexity.
  • standard math Concentration inequalities for self-normalized processes and epsilon-net covering bounds from Abbasi-Yadkori et al. and Jin et al.
    Used to obtain the uniform high-probability event in Lemma 4 and Lemma 12; these are background results cited from the prior literature.

how reviews work

0 comments
Cite this review

Pith. "Pith review of A Computationally Efficient Algorithm for Infinite-Horizon Average-Reward Linear MDPs." pith.science (2026). https://pith.science/paper/YZOYZIQJ

@misc{pith2026250411997,
  author       = {Pith},
  title        = {Pith review of: A Computationally Efficient Algorithm for Infinite-Horizon Average-Reward Linear MDPs},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/YZOYZIQJ}},
  note         = {Machine review of arXiv:2504.11997}
}
read the original 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.

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

26 extracted references · 23 canonical work pages

  1. [1]

    Improved algorithms for linear stochastic bandits

    Y asin Abbasi-Y adkori, Dávid Pál, and Csaba Szepesvári. “Improved algorithms for linear stochastic bandits”. In: Advances in neural information processing systems 24 (2011)

    work page 2011

  2. [2]

    Near-opt imal regret bounds for reinforcement learn- ing

    Peter Auer, Thomas Jaksch, and Ronald Ortner. “Near-opt imal regret bounds for reinforcement learn- ing”. In: Advances in neural information processing systems 21 (2008)

    work page 2008

  3. [3]

    Model-based reinforcement learning with value-targeted regression

    Alex Ayoub, Zeyu Jia, Csaba Szepesvari, Mengdi Wang, and Lin Y ang. “Model-based reinforcement learning with value-targeted regression”. In: International Conference on Machine Learning. PMLR. 2020, pp. 463–474. 12

    work page 2020

  4. [4]

    REGAL: a regularizati on based algorithm for reinforcement learn- ing in weakly communicating MDPs

    Peter Bartlett and Ambuj Tewari. “REGAL: a regularizati on based algorithm for reinforcement learn- ing in weakly communicating MDPs”. In: Uncertainty in Artificial Intelligence: Proceedings of the 25th Conference. AUAI Press. 2009, pp. 35–42

    work page 2009

  5. [5]

    Learning Infinite- Horizon Average-Reward Linear Mixture MDPs of Bounded Span

    Woojin Chae, Kihyuk Hong, Y ufan Zhang, Ambuj Tewari, and Dabeen Lee. Learning Infinite- Horizon Average-Reward Linear Mixture MDPs of Bounded Span . 2025

    work page 2025

  6. [6]

    Efficient bias-span- constrained exploration-exploitation in reinforcement l earning

    Ronan Fruit, Matteo Pirotta, Alessandro Lazaric, and Ro nald Ortner. “Efficient bias-span- constrained exploration-exploitation in reinforcement l earning”. In: International Conference on Machine Learning. PMLR. 2018, pp. 1578–1586

    work page 2018

  7. [7]

    Inven tory management in supply chains: a re- inforcement learning approach

    Ilaria Giannoccaro and Pierpaolo Pontrandolfo. “Inven tory management in supply chains: a re- inforcement learning approach”. In: International Journal of Production Economics 78.2 (2002), pp. 153–161

    work page 2002

  8. [8]

    Can deep reinforce- ment learning improve inventory management? performance o n lost sales, dual-sourcing, and multi- echelon problems

    Joren Gijsbrechts, Robert N Boute, Jan A V an Mieghem, and Dennis J Zhang. “Can deep reinforce- ment learning improve inventory management? performance o n lost sales, dual-sourcing, and multi- echelon problems”. In: Manufacturing & Service Operations Management 24.3 (2022), pp. 1349– 1368

    work page 2022

Show all 26 references
  1. [9]

    Reinforcement learning for long-run a verage cost

    Abhijit Gosavi. “Reinforcement learning for long-run a verage cost”. In: European journal of opera- tional research 155.3 (2004), pp. 654–674

    2004

  2. [10]

    Sample-effi cient Learning of Infinite-horizon Average-reward MDPs with General Function Approximation

    Jianliang He, Han Zhong, and Zhuoran Y ang. “Sample-effi cient Learning of Infinite-horizon Average-reward MDPs with General Function Approximation” . In: The Twelfth International Con- ference on Learning Representations . 2024

    2024

  3. [11]

    Reinforcement Learn- ing for Infinite-Horizon Average-Reward Linear MDPs via App roximation by Discounted-Reward MDPs

    Kihyuk Hong, Woojin Chae, Y ufan Zhang, Dabeen Lee, and A mbuj Tewari. “Reinforcement Learn- ing for Infinite-Horizon Average-Reward Linear MDPs via App roximation by Discounted-Reward MDPs”. In: International Conference on Artificial Intelligence and St atistics. 2025

    2025

  4. [12]

    Provably efficient reinforcement learning with linear function approximation

    Chi Jin, Zhuoran Y ang, Zhaoran Wang, and Michael I Jorda n. “Provably efficient reinforcement learning with linear function approximation”. In: Conference on learning theory . PMLR. 2020, pp. 2137–2143

    2020

  5. [13]

    Towards tight bounds on th e sample complexity of average-reward MDPs

    Y ujia Jin and Aaron Sidford. “Towards tight bounds on th e sample complexity of average-reward MDPs”. In: International Conference on Machine Learning . PMLR. 2021, pp. 5055–5064

    2021

  6. [14]

    Reinforcement learning based routin g in networks: Review and classification of approaches

    Zoubir Mammeri. “Reinforcement learning based routin g in networks: Review and classification of approaches”. In: Ieee Access 7 (2019), pp. 55916–55950

    2019

  7. [15]

    Sample complexity of reinforcement learning using linearly combined model ensembles

    Aditya Modi, Nan Jiang, Ambuj Tewari, and Satinder Sing h. “Sample complexity of reinforcement learning using linearly combined model ensembles”. In: International Conference on Artificial Intel- ligence and Statistics. PMLR. 2020, pp. 2010–2020

    2020

  8. [16]

    Near sample- optimal reduction-based policy learn- ing for average reward mdp

    Jinghan Wang, Mengdi Wang, and Lin F Y ang. “Near sample- optimal reduction-based policy learn- ing for average reward mdp”. In: arXiv preprint arXiv:2212.00603 (2022)

    2022 arXiv

  9. [17]

    Optimal Sample Complexity for Average Reward Markov Decision Processes

    Shengbo Wang, Jose Blanchet, and Peter Glynn. “Optimal Sample Complexity for Average Reward Markov Decision Processes”. In: arXiv preprint arXiv:2310.08833 (2023)

    2023 arXiv

  10. [18]

    Learning infinite-horizon average-reward mdps with linear function approximation

    Chen-Y u Wei, Mehdi Jafarnia Jahromi, Haipeng Luo, and R ahul Jain. “Learning infinite-horizon average-reward mdps with linear function approximation”. In: International Conference on Artificial Intelligence and Statistics. PMLR. 2021, pp. 3007–3015

    2021

  11. [19]

    Model-free reinforcement learning in infinite-horizon average-rewar d markov decision processes

    Chen-Y u Wei, Mehdi Jafarnia Jahromi, Haipeng Luo, Hite shi Sharma, and Rahul Jain. “Model-free reinforcement learning in infinite-horizon average-rewar d markov decision processes”. In: Interna- tional conference on machine learning . PMLR. 2020, pp. 10170–10180. 13

    2020

  12. [20]

    Nearly minimax o ptimal regret for learning infinite- horizon average-reward mdps with linear function approxim ation

    Y ue Wu, Dongruo Zhou, and Quanquan Gu. “Nearly minimax o ptimal regret for learning infinite- horizon average-reward mdps with linear function approxim ation”. In: International Conference on Artificial Intelligence and Statistics . PMLR. 2022, pp. 3883–3913

    2022

  13. [21]

    Joint optimiz ation of preventive maintenance and production scheduling for multi-state production systems based on reinforcement learning

    Hongbing Y ang, Wenchao Li, and Bin Wang. “Joint optimiz ation of preventive maintenance and production scheduling for multi-state production systems based on reinforcement learning”. In: Re- liability Engineering & System Safety 214 (2021), p. 107713

    2021

  14. [22]

    Regret minimization for reinforcement learning by evaluating the optimal bias function

    Zihan Zhang and Xiangyang Ji. “Regret minimization for reinforcement learning by evaluating the optimal bias function”. In: Advances in Neural Information Processing Systems 32 (2019)

    2019

  15. [23]

    Sharper Model-free Reinf orcement Learning for Average-reward Markov Decision Processes

    Zihan Zhang and Qiaomin Xie. “Sharper Model-free Reinf orcement Learning for Average-reward Markov Decision Processes”. In: The Thirty Sixth Annual Conference on Learning Theory . PMLR. 2023, pp. 5476–5477

    2023

  16. [24]

    Span-Based Optimal Sam ple Complexity for Average Reward MDPs

    Matthew Zurek and Y udong Chen. “Span-Based Optimal Sam ple Complexity for Average Reward MDPs”. In: arXiv preprint arXiv:2311.13469 (2023). 14 A Concentration Inequalities Lemma 8 (Concentration of vector-valued self-normalized process es [ 1]). Let{εt}∞ t=1 be a real-valued ...

    2023 arXiv

  17. [25]

    If n is odd, we can take φ n = 0 and similar argument holds

    For convenience, let n = 2 m. If n is odd, we can take φ n = 0 and similar argument holds. Take φ 1, . . .φ m = ( η, 1/2, 0, . . . ,0) and φ m+1, . . . ,φ 2m = ( η,−1/2, 0, . . . ,0) where η > 0 is to be chosen later. Take y1 =··· = y2m = ∆ and λ = 1 . Then, Λ n = diag(η2n, n/...

  18. [26]

    By Lemma 6, we have for t≥ 4, Qt u(s, a)≤ r(s, a) + γ[P V t u+1](s, a) + 2β‖ϕ (s, a)‖Λ −1 t + 2(mt−3− mt)

    We prove under the event E defined in Lemma 12, which occurs with probability at least 1− δ. By Lemma 6, we have for t≥ 4, Qt u(s, a)≤ r(s, a) + γ[P V t u+1](s, a) + 2β‖ϕ (s, a)‖Λ −1 t + 2(mt−3− mt). Plugging in u← t, s← st, a← at, we get RT = T∑ t=1 (J ∗− r(st, at)) ≤ T∑ t=4 (...

Pith tools

Reviewed August 16, 2026 · model on record in the stance chip above.