Pith. sign in

REVIEW 1 major objections 4 minor 1 cited by

Near-Optimal Sample Complexity for MDPs via Anchoring

T0 review · 1 major / 4 minor · reviewed 2026-08-08 · deepseek-v4-flash

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

Pith's one-line read A model-free anchored iteration solves average-reward MDPs near-optimally, with no prior knowledge of the bias vector.

desk verdict Solid theory paper: a parameter-free model-free algorithm for weakly communicating average-reward MDPs with near-optimal sample complexity, and the proofs hold up. read the letter →

arxiv 2502.04477 v2 pith:DIQJ7VWG submitted 2025-02-06 math.OC cs.DS

Jongmin Lee , Mario Bravo , Roberto Cominetti This is my paper · ORCID
classification math.OCcs.DS MSC 90C4068W20
keywords average-rewardMDPssamplecomplexitymodel-freereinforcementlearningHalpernanchorediterationweaklycommunicatingMDPrecursivesamplingBellmanresidualgenerativemodel
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

This paper claims that average-reward Markov decision processes can be solved near-optimally by a model-free algorithm that needs no prior information about the problem's hardness. The algorithm, SAVIA+, combines Halpern's anchored iteration with recursive sampling, and returns an $\varepsilon$-optimal policy with sample and time complexity $\widetilde{O}(|\mathcal{S}||\mathcal{A}|\|h^*\|_{\mathrm{sp}}^2/\varepsilon^2)$, both with high probability and in expectation. This matches the known lower bound up to a factor $\|h^*\|_{\mathrm{sp}}$, the span of the unknown bias vector, and it is the best reported among model-free methods. The same ideas give a near-optimal algorithm for discounted MDPs.

What carries the argument

The central object is Halpern's anchored iteration $Q_{k+1}=(1-\beta_{k+1})Q_0+\beta_{k+1}T(Q_k)$ with $\beta_k=k/(k+2)$, interpreted modulo additive constants so the unknown optimal gain $g^*$ drops out. Because the Bellman operator is nonexpansive, anchored iteration drives the residual to zero at rate $4\|Q_0-Q^*\|_{\mathrm{sp}}/(k+1)$, and the paper's Proposition 2.1 converts any small residual into an $\varepsilon$-optimal greedy policy via $g^*-g_\pi(s)\le\|Q-T(Q)\|_{\mathrm{sp}}$. The recursion is implemented with recursive sampling, a variance-reduction step that approximates $T(Q_k)$ by accumulating samples of the differences $d_k$; the sample count per round is set by $\|d_k\|_{\mathrm{sp}}$, not by $\|Q_k\|_{\mathrm{sp}}$. The stopping rule on the empirical residual $\|Q_n-T_n\|_{\mathrm{sp}}$ makes the loop count self-tuning.

What would settle it

Run SAVIA+ from $Q_0=0$ on a family of weakly communicating MDPs with small state and action spaces and with rewards tuned so that $\|h^*\|_{\mathrm{sp}}$ takes values such as $1,2,4,8$, fixing a small $\varepsilon$ and recording the number of generative samples until the empirical residual first falls below $14\varepsilon$. If the measured sample growth in $\|h^*\|_{\mathrm{sp}}$ is consistently worse than quadratic, or if on a successful run $g^*-g_\pi(s)>16\varepsilon$ for some state, the theorem is contradicted; the expectation version can be checked by averaging over many runs with $\delta=\varepsilon^2/17$.

Watch

Extended reading notes

Core claim

Under the standing assumption that the MDP is weakly communicating, the paper proves that a Halpern anchored value iteration run with the Bellman operator $T(Q)=r+P\max_A Q$ evaluated by recursive sampling reduces the Bellman residual $\|Q_k-T(Q_k)\|_{\mathrm{sp}}$ fast enough that the greedy policy of $Q_k$ is $\varepsilon$-optimal after $O(\|Q_0-Q^*\|_{\mathrm{sp}}/\varepsilon)$ iterations. A doubling trick plus a stopping rule on the empirical residual makes the procedure parameter-free: it terminates with probability $1$, and the total sample and time complexity is $\widetilde{O}(|\mathcal{S}||\mathcal{A}|\|h^*\|_{\mathrm{sp}}^2/\varepsilon^2)$ in high probability and in expectation. The key to matching the quadratic $\varepsilon$ dependence is estimating the Bellman operator incrementally as a sum of sampled differences $d_k=\max_A Q_k-\max_A Q_{k-1}$, so the variance of each sample is proportional to the small span of $d_k$ rather than to the full size of the $Q$-function.

Load-bearing premise

The load-bearing premise is that the MDP is weakly communicating (Assumption (H)): there is a single optimal average reward shared by all states and a bias vector that solves Bellman's equation. If the MDP is multichain, the residual bound no longer yields a uniform $\varepsilon$-optimal policy, and the stated complexity is not proven.

Editorial extensions

If this is right

  • SAVIA+ closes most of the gap between previous model-free average-reward methods and the known lower bound, reducing the $\varepsilon$ dependence to $1/\varepsilon^2$ and making the span factor $\|h^*\|_{\mathrm{sp}}^2$ the leading problem-dependent term.
  • Because no prior estimate of $\|h^*\|_{\mathrm{sp}}$ or of the mixing time is needed, the algorithm can be run as-is on any weakly communicating MDP; the empirical-residual stopping rule guarantees finite termination with probability $1$.
  • The same anchored iteration with recursive sampling attains, for discounted MDPs, the best known Bellman-residual sample complexity $\widetilde{O}(|\mathcal{S}||\mathcal{A}|/((1-\gamma)^2\varepsilon^2))$, and a policy complexity $\widetilde{O}(|\mathcal{S}||\mathcal{A}|\|Q^*\|_\infty^2/((1-\gamma)^2\varepsilon^2))$.
  • Expected sample complexity and expected policy error are also controlled, so the method gives finite-time guarantees that hold not only on a high-probability event but over the full probability space.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • The factor $\|h^*\|_{\mathrm{sp}}$ separating SAVIA+ from the lower bound may be removable by a finer policy-error analysis or a different anchor schedule; if so, the complexity would be fully optimal for weakly communicating MDPs.
  • The quotient-space view of anchoring, working modulo additive constants, suggests the method extends to multichain MDPs by tracking a bias vector per recurrent class and stopping only when the residual is small in every class, though the paper does not analyze this.
  • The recursive-difference sampling idea is transferable to any nonexpansive fixed-point iteration with an incremental linear part; one testable extension is applying it to average-reward MDPs under episodic or online sampling instead of the generative model.
  • A concrete practitioner check: on a two-state weakly communicating MDP, the per-iteration sample count $m_k$ should track $\|h_k-h_{k-1}\|_{\mathrm{sp}}^2$, not $\|h_k\|_{\mathrm{sp}}^2$; instrumenting the algorithm would reveal whether the variance reduction is acting as the proof requires.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

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

Referee Report

1 major / 4 minor

Summary. The paper proposes a model-free stochastic anchored value iteration for average-reward Markov decision processes in the weakly communicating setting. SAVIA combines Halpern's anchored iteration with recursive sampling to estimate Bellman residuals, and SAVIA+ adds a doubling trick and an empirical-residual stopping rule so that no prior knowledge of the mixing time, diameter, or bias span is required. The main results (Theorems 3.2, 3.4, and 3.6, with Corollaries 3.5 and 3.7) establish an eO(|S||A| ||h*||_sp^2 / eps^2) sample and time complexity for computing an eps-optimal policy, both with high probability and in expectation, for weakly communicating MDPs. A discounted analogue (SAVID/SAVID+) is analyzed in Section 4.

Significance. If the results hold, the paper is a significant advance: it removes the prior-knowledge requirement that most earlier model-free and model-based algorithms for average-reward MDPs impose, while preserving the best known model-free rate up to the factor ||h*||_sp. The core average-reward proof chain is transparent and mostly self-contained: Proposition 2.1 is a valid adaptation of Puterman's residual bound under the scalar-gain assumption, Proposition 3.1 is a correct Azuma-Hoeffding argument for the recursive-sampling martingale, and the stopping-time and expectation arguments in Theorems 3.4 and 3.6 are coherent. The algorithm is genuinely parameter-free: the sequences beta_k and c_k, the initial value Q0=0, and the stopping threshold are fixed, while ||h*||_sp appears only in the instance-dependent bound. The scope is explicitly limited by Assumption (H) to weakly communicating MDPs; this is a real limitation, but it is stated precisely and is exactly what makes the optimal gain a scalar in Proposition 2.1.

major comments (1)
  1. [Section 4.2, Algorithm 4 / Appendix B, Proposition B.1] The discounted sampling budget appears inconsistent with the proof as written. Algorithm 4 sets m_k = ceil(2 alpha c_k ||d_k||_infty^2 / eps^2), while the proof of Proposition B.1 says it follows 'in the exact same manner' as Proposition 3.1. In the average-reward proof the conditional Hoeffding term is (1/2) lambda^2 ||d_k||_sp^2 / m_k, and the choice m_k = alpha c_k ||d_k||_sp^2 / eps^2 gives a per-step term (1/2) lambda^2 eps^2 / (alpha c_k). In the discounted case ||d_k||_sp^2 <= 4 ||d_k||_infty^2, so the same calculation with Algorithm 4's m_k gives ||d_k||_sp^2 / m_k <= 2 eps^2 / (alpha c_k), and the cumulative Azuma-Hoeffding tail bound becomes exp(-alpha/2) rather than exp(-alpha). Thus the stated probability bound in Proposition B.1, and consequently Theorems 4.2 and 4.3, do not follow from the proof as written. The gap is local and fixable: either set m_k = ceil(4 alpha c_k ||d_k||_infty^2 / eps^2), or use the sharp range-based Hoeffding inequality (with the range span(d_k)/m_k in place of the looser |X| <= c bound used in the average-reward proof), which restores the claimed bound without changing the asymptotic complexity.
minor comments (4)
  1. [Abstract and Corollary 3.7] The abstract says the clean eO(|S||A| ||h*||_sp^2 / eps^2) bound holds 'both in high probability and in expectation' without qualification. Theorem 3.6's expected complexity contains an extra delta(1+mu/eps)^2(1+(kappa/eps)^2) term; the clean expected rate is obtained only after the particular choice delta = eps^2/17 in Corollary 3.7. The wording should be qualified or the statement should reference the specific delta choice.
  2. [Appendix A.3, proof of Theorem 3.6] In the proof of Theorem 3.6 the good event is written as B = cap_{i=1}^infty G_i, whereas it should start at i=0 to include the first doubling loop, as in the proof of Theorem 3.4. This is a typo, but it should be corrected.
  3. [Section 2.2 and after Corollary 3.5] The text refers to 'Theorem 2.1' in the sentence 'Combining Theorem 2.1 with the general estimate...' and to 'Theorem 3.5' in the sentence after Corollary 3.5; both should refer to Proposition 2.1 and Corollary 3.5 respectively.
  4. [Remark after Proposition 3.1] The remark says 'A direct consequence of Theorem 3.1 is...' but the statement in question is Proposition 3.1; the cross-reference should be updated.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the algorithm is parameter-free and the complexity bounds are derived from external fixed-point and concentration results, not from its own conclusions.

full rationale

The derivation chain is self-contained. The policy-quality link (Proposition 2.1, Appendix A.1) is proven directly from standard MDP theory, with the proof included in the paper. The Halpern residual bound is imported from Sabach & Shtern (2017), an external source, and the paper explicitly gives the remaining analysis in Lemmas A.1, A.2, and Theorem 3.2. The recursive-sampling concentration (Proposition 3.1, Appendix A.2) is a martingale/Hoeffding argument with all measurability and sample-size dependencies stated; it does not assume the conclusion. The stopping rule in SAVIA+ is based on an empirical residual, and the proof that it terminates and yields a policy with small error uses only the residual-to-policy bound, the concentration bound, and the independence of restarts. The complexity bound is instance-dependent through ||h*||_sp, but no algorithm parameter is set using ||h*||_sp; Q0=0 and beta_k, c_k are fixed sequences. The claimed near-optimality is compared to external lower bounds. Self-citations (Bravo & Contreras 2024; Lee & Ryu 2023, 2025) are contextual and not load-bearing: the central tools come from Sabach & Shtern, Puterman, and Jin et al. No fitted input is renamed as a prediction, and no uniqueness theorem from the authors is used to force a choice. The paper's own limitation, Assumption (H), is explicit and does not create circularity. Therefore no circular step can be exhibited from the paper's equations.

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

The central claim rests on Assumption (H) (weak communication), the generative-model sampling model, and standard results: Puterman's Bellman equation theory, the Sabach-Shtern Halpern residual bound, Azuma's inequality, and the Wang et al. (2022) lower bound used for the near-optimality statement. The algorithm's only design choices are the sequences beta_k and c_k and the stopping thresholds, none of which are fitted to data. No new physical or mathematical entities are postulated.

free parameters (4)
  • beta_k = k/(k+2)
    Averaging sequence for the anchored Halpern iteration, chosen to match the convergence condition of Sabach & Shtern (2017).
  • c_k = 5(k+2) ln^2(k+2)
    Sampling sequence chosen so that 2*sum(c_k^{-1}) <= 1 and to balance the concentration bound with sample complexity.
  • stopping threshold for SAVIA+ = 14*eps
    Empirical Bellman residual threshold in Algorithm 3; the constant 14 is chosen so that the good-event bound yields the desired policy error.
  • discounted stopping threshold = 11*eps
    Empirical Bellman residual threshold in SAVID+ (Algorithm 5), chosen analogously to the average-reward case.
assumptions (6)
  • domain assumption The MDP is weakly communicating (Assumption (H))
    Section 1.2 assumes (H); it ensures g* is constant across states and a bias vector h* exists. All main theorems are stated under (H).
  • domain assumption Generative model supplies independent samples from P(.|s,a) for every (s,a)
    Stated in the abstract and used in Algorithm 1 (SAMPLE) and in the martingale argument of Proposition 3.1.
  • standard math Sabach-Shtern (2017, Lemma 5) Halpern iteration error bound
    Used in Section 2.2 and Section C to bound the Bellman residual of the anchored iteration by 4/(k+1) ||Q0 - Q*||_sp.
  • standard math Azuma-Hoeffding inequality
    Core concentration tool in Proposition 3.1 for the recursive sampling error.
  • standard math Puterman (2014) Bellman equation results for weakly communicating MDPs
    Existence of solutions, constant gain, and greedy policy optimality; used in Sections 1.2 and 2.2.
  • standard math Wang et al. (2022) lower bound Omega( |S||A| ||h*||_sp / eps^2 )
    External lower bound that justifies the 'near-optimal' claim; not proved in this paper.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Near-Optimal Sample Complexity for MDPs via Anchoring." pith.science (2026). https://pith.science/paper/DIQJ7VWG

@misc{pith2026250204477,
  author       = {Pith},
  title        = {Pith review of: Near-Optimal Sample Complexity for MDPs via Anchoring},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/DIQJ7VWG}},
  note         = {Machine review of arXiv:2502.04477}
}
abstract

We study a new model-free algorithm to compute $\varepsilon$-optimal policies for average reward Markov decision processes, in the weakly communicating case. Given a generative model, our procedure combines a recursive sampling technique with Halpern's anchored iteration, and computes an $\varepsilon$-optimal policy with sample and time complexity $\widetilde{O}(|\mathcal{S}||\mathcal{A}|\|h^*\|_{\text{sp}}^{2}/\varepsilon^{2})$ both in high probability and in expectation. To our knowledge, this is the best complexity among model-free algorithms, matching the known lower bound up to a factor $\|h^*\|_{\text{sp}}$. Although the complexity bound involves the span seminorm $\|h^*\|_{\text{sp}}$ of the unknown bias vector, the algorithm requires no prior knowledge and implements a stopping rule which guarantees with probability 1 that the procedure terminates in finite time. We also analyze how these techniques can be adapted for discounted MDPs.

Discussion (0). Continue with ORCID to comment.

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score. Full citation record

  1. Auto-exploration for online reinforcement learning

    cs.LG 2025-12 conditional novelty 6.0 of 10

    New parameter-free SPMD algorithms achieve the first algorithm-independent O(ε⁻²) sample complexity for online discounted RL under a mixing-optimal-policy assumption.

Reference graph

Works this paper leans on

65 extracted references · 59 canonical work pages · cited by 1 Pith paper

  1. [1]

    Agarwal, A., Kakade, S., and Yang, L. F. Model-based reinforcement learning with a generative model is minimax optimal. Conference on Learning Theory, 2020

    work page 2020

  2. [2]

    Auer, P., Cesa-Bianchi, N., Freund, Y., and Schapire, R. E. Gambling in a rigged casino: The adversarial multi-armed bandit problem. Proceedings of IEEE 36th Annual Foundations of Computer Science, pp.\ 322--331, 1995

    work page 1995

  3. [3]

    G., Munos, R., and Kappen, H

    Azar, M. G., Munos, R., and Kappen, H. J. Minimax PAC bounds on the sample complexity of reinforcement learning with a generative model. Machine Learning, 91 0 (3): 0 325--349, 2013

    work page 2013

  4. [4]

    Weighted sums of certain dependent random variables

    Azuma, K. Weighted sums of certain dependent random variables. Tohoku Mathematical Journal, Second Series, 19 0 (3): 0 357--367, 1967

    work page 1967

  5. [5]

    U., and Aggarwal, V

    Bai, Q., Mondal, W. U., and Aggarwal, V. Regret analysis of policy gradient algorithm for infinite horizon average reward markov decision processes. International Conference on Artificial Intelligence, 2024

    work page 2024

  6. [6]

    A M arkovian decision process

    Bellman, R. A M arkovian decision process. Journal of Mathematics and Mechanics, 6 0 (5): 0 679--684, 1957

    work page 1957

  7. [7]

    Bertsekas, D. P. Dynamic Programming and Optimal Control, volume II. Athena Scientific, 4th edition, 2012

    work page 2012

  8. [8]

    Bertsekas, D. P. and Tsitsiklis, J. N. Neuro-Dynamic Programming. Athena Scientific , 1996

    work page 1996

Show all 65 references
  1. [9]

    and Kaufmann, E

    Besson, L. and Kaufmann, E. What doubling tricks can and can't do for multi-armed bandits. arXiv preprint arXiv:1803.06971, 2018

    2018 arXiv

  2. [10]

    Discrete dynamic programming

    Blackwell, D. Discrete dynamic programming. The Annals of Mathematical Statistics, 33: 0 719--726, 1962

    1962

  3. [11]

    Bourel, H., Jonsson, A., Maillard, O.-A., and Talebi, M. S. Exploration in reward machines with low regret. International Conference on Artificial Intelligence and Statistics, 2023

    2023

  4. [12]

    and Contreras, J

    Bravo, M. and Contreras, J. P. Stochastic H alpern iteration in normed spaces and applications to reinforcement learning. arXiv preprint arXiv:2403.12338, 2024

    2024 arXiv

  5. [13]

    Stochastic H alpern iteration with variance reduction for stochastic monotone inclusions

    Cai, X., Song, C., Guzm \'a n, C., and Diakonikolas, J. Stochastic H alpern iteration with variance reduction for stochastic monotone inclusions. Neural Information Processing Systems, 2022

    2022

  6. [14]

    Contreras, J. P. and Cominetti, R. Optimal error bounds for non-expansive fixed-point iterations in normed spaces. Mathematical Programming, 199 0 (1--2): 0 343--374, 2022

    2022

  7. [15]

    Average-reward model-free reinforcement learning: a systematic review and literature mapping

    Dewanto, V., Dunn, G., Eshragh, A., Gallagher, M., and Roosta, F. Average-reward model-free reinforcement learning: a systematic review and literature mapping. arXiv preprint arXiv:2010.08920, 2020

    2010 arXiv

  8. [16]

    Tree-based batch mode reinforcement learning

    Ernst, D., Geurts, P., and Wehenkel, L. Tree-based batch mode reinforcement learning. Journal of Machine Learning Research, 2005

    2005

  9. [17]

    Regret minimization in MDP s with options without prior knowledge

    Fruit, R., Pirotta, M., Lazaric, A., and Brunskill, E. Regret minimization in MDP s with options without prior knowledge. Neural Information Processing Systems, 2017

    2017

  10. [18]

    Fixed points of nonexpanding maps

    Halpern, B. Fixed points of nonexpanding maps. Bulletin of the American Mathematical Society, 73 0 (6): 0 957--961, 1967

    1967

  11. [19]

    Howard, R. A. Dynamic Programming and M arkov Processes. John Wiley and Sons, 1960

    1960

  12. [20]

    and Sidford, A

    Jin, Y. and Sidford, A. Efficiently solving MDP s with stochastic mirror descent. International Conference on Machine Learning, 2020

    2020

  13. [21]

    and Sidford, A

    Jin, Y. and Sidford, A. Towards tight bounds on the sample complexity of average-reward MDP s. International Conference on Machine Learning, 2021

    2021

  14. [22]

    Feasible Q -learning for average reward reinforcement learning

    Jin, Y., Gummadi, R., Zhou, Z., and Blanchet, J. Feasible Q -learning for average reward reinforcement learning. International Conference on Artificial Intelligence and Statistics, 2024 a

    2024

  15. [23]

    Truncated variance reduced value iteration

    Jin, Y., Karmarkar, I., Sidford, A., and Wang, J. Truncated variance reduced value iteration. Neural Information Processing Systems, 2024 b

    2024

  16. [24]

    and Zhang, T

    Johnson, R. and Zhang, T. Accelerating stochastic gradient descent using predictive variance reduction. Neural information processing systems, 2013

    2013

  17. [25]

    An -best-arm identification algorithm for fixed-confidence and beyond

    Jourdan, M., Degenne, R., and Kaufmann, E. An -best-arm identification algorithm for fixed-confidence and beyond. Neural Information Processing Systems, 2023

    2023

  18. [26]

    and Jamieson, K

    Katz-Samuels, J. and Jamieson, K. The true sample complexity of identifying good arms. International Conference on Artificial Intelligence and Statistics, 2020

    2020

  19. [27]

    and Singh, S

    Kearns, M. and Singh, S. Finite-sample convergence rates for Q -learning and indirect algorithms. Neural Information Processing Systems, 1998

    1998

  20. [28]

    Accelerated proximal point method for maximally monotone operators

    Kim, D. Accelerated proximal point method for maximally monotone operators. Mathematical Programming, 190 0 (1--2): 0 57--87, 2021

    2021

  21. [29]

    Y., and Mannor, S

    Kumar, N., Wang, K., Levy, K. Y., and Mannor, S. Efficient value iteration for s-rectangular robust M arkov decision processes. International Conference on Machine Learning, 2024

    2024

  22. [30]

    Y., Srikant, R., and Mannor, S

    Kumar, N., Murthy, Y., Shufaro, I., Levy, K. Y., Srikant, R., and Mannor, S. On the global convergence of policy gradient in average reward M arkov decision processes. International Conference on Learning Representations, 2025

    2025

  23. [31]

    and Ryu, E

    Lee, J. and Ryu, E. Accelerating value iteration with anchoring. Neural Information Processing Systems, 2023

    2023

  24. [32]

    and Ryu, E

    Lee, J. and Ryu, E. Optimal non-asymptotic rates of value iteration for average-reward MDP s. International Conference on Learning Representations, 2025

    2025

  25. [33]

    Breaking the sample size barrier in model-based reinforcement learning with a generative model

    Li, G., Wei, Y., Chi, Y., Gu, Y., and Chen, Y. Breaking the sample size barrier in model-based reinforcement learning with a generative model. Neural Information Processing Systems, 2020

    2020

  26. [34]

    Stochastic first-order methods for average-reward M arkov decision processes

    Li, T., Wu, F., and Lan, G. Stochastic first-order methods for average-reward M arkov decision processes. Mathematics of Operations Research, 2024

    2024

  27. [35]

    On the convergence rate of the H alpern-iteration

    Lieder, F. On the convergence rate of the H alpern-iteration. Optimization Letters, 15 0 (2): 0 405--418, 2021

    2021

  28. [36]

    Average reward reinforcement learning: Foundations, algorithms, and empirical results

    Mahadevan, S. Average reward reinforcement learning: Foundations, algorithms, and empirical results. Machine Learning, 22 0 (1): 0 159--195, 1996

    1996

  29. [37]

    Finding all -good arms in stochastic bandits

    Mason, B., Jain, L., Tripathy, A., and Nowak, R. Finding all -good arms in stochastic bandits. Neural Information Processing Systems, 2020

    2020

  30. [38]

    A., and et al

    Mnih, V., Kavukcuoglu, K., Silver, D., Rusu, A. A., and et al. Human-level control through deep reinforcement learning. Nature, 518 0 (7540): 0 529--533, 2015

    2015

  31. [39]

    and Szepesv \'a ri, C

    Munos, R. and Szepesv \'a ri, C. Finite-time bounds for fitted value iteration. Journal of Machine Learning Research, 2008

    2008

  32. [40]

    and Srikant, R

    Murthy, Y. and Srikant, R. On the convergence of natural policy gradient and mirror descent-like policy methods for average-reward MDP s. IEEE Conference on Decision and Control, pp.\ 1979--1984, 2023

    1979

  33. [41]

    and Okolo, N

    Neu, G. and Okolo, N. Dealing with unbounded gradients in stochastic saddle-point optimization. International Conference on Machine Learning, 2024

    2024

  34. [42]

    M., Liu, J., Scheinberg, K., and Tak \'a c , M

    Nguyen, L. M., Liu, J., Scheinberg, K., and Tak \'a c , M. Sarah: A novel method for machine learning problems using stochastic recursive gradient. International Conference on Machine Learning, 2017

    2017

  35. [43]

    and Ryu, E

    Park, J. and Ryu, E. K. Exact optimal accelerated complexity for fixed-point iterations. International Conference on Machine Learning, 2022

    2022

  36. [44]

    Puterman, M. L. M arkov Decision Processes: Discrete Stochastic Dynamic Programming . John Wiley and Sons, 2nd edition, 2014

    2014

  37. [45]

    Strong convergence theorems for resolvents of accretive operators in B anach spaces

    Reich, S. Strong convergence theorems for resolvents of accretive operators in B anach spaces. Journal of Mathematical Analysis and Applications, 75 0 (1): 0 287--292, 1980

    1980

  38. [46]

    and Mansour, Y

    Rosenberg, A. and Mansour, Y. Oracle-efficient regret minimization in factored MDP s with unknown structure. Neural Information Processing Systems, 2021

    2021

  39. [47]

    and Shtern, S

    Sabach, S. and Shtern, S. A first order method for solving convex bilevel optimization problems. SIAM Journal on Optimization, 27 0 (2): 0 640--660, 2017

    2017

  40. [48]

    Near-optimal time and sample complexities for solving M arkov decision processes with a generative model

    Sidford, A., Wang, M., Wu, X., Yang, L., and Ye, Y. Near-optimal time and sample complexities for solving M arkov decision processes with a generative model. Neural Information Processing Systems, 2018

    2018

  41. [49]

    Variance reduced value iteration and faster algorithms for solving M arkov decision processes

    Sidford, A., Wang, M., Wu, X., and Ye, Y. Variance reduced value iteration and faster algorithms for solving M arkov decision processes. Naval Research Logistics, 70 0 (5): 0 423--442, 2023

    2023

  42. [50]

    Sutton, R. S. Learning to predict by the methods of temporal differences. Machine Learning, 3: 0 9--44, 1988

    1988

  43. [51]

    Sutton, R. S. and Barto, A. G. Reinforcement Learning: An introduction. MIT press, 2nd edition, 2018

    2018

  44. [52]

    Algorithms for Reinforcement Learning

    Szepesv\'ari, C . Algorithms for Reinforcement Learning. Morgan Claypool Publishers, 2010

    2010

  45. [53]

    Finding good policies in average-reward M arkov decision processes without prior knowledge

    Tuynman, A., Degenne, R., and Kaufmann, E. Finding good policies in average-reward M arkov decision processes without prior knowledge. Neural Information Processing Systems, 2024

    2024

  46. [54]

    Wainwright, M. J. Variance-reduced Q -learning is minimax optimal. arXiv preprint arXiv:1906.04697, 2019

    1906 arXiv

  47. [55]

    Wan, Y., Naik, A., and Sutton, R. S. Learning and planning in average-reward M arkov decision processes. International Conference on Machine Learning, 2021

    2021

  48. [56]

    Wang, J., Wang, M., and Yang, L. F. Near sample-optimal reduction-based policy learning for average reward MDP . arXiv:2212.00603, 2022

    2022 arXiv

  49. [57]

    Primal-dual learning: Sample complexity and sublinear run time for ergodic M arkov decision problems

    Wang, M. Primal-dual learning: Sample complexity and sublinear run time for ergodic M arkov decision problems. arXiv:1710.06100, 2017

    2017 arXiv

  50. [58]

    Optimal sample complexity for average reward M arkov decision processes

    Wang, S., Blanchet, J., and Glynn, P. Optimal sample complexity for average reward M arkov decision processes. International Conference on Learning Representations, 2023

    2023

  51. [59]

    J., Luo, H., Sharma, H., and Jain, R

    Wei, C.-Y., Jahromi, M. J., Luo, H., Sharma, H., and Jain, R. Model-free reinforcement learning in infinite-horizon average-reward M arkov decision processes. International Conference on Machine Learning, 2020

    2020

  52. [60]

    Approximation of fixed points of nonexpansive mappings

    Wittmann, R. Approximation of fixed points of nonexpansive mappings. Archiv der Mathematik, 58 0 (5): 0 486--491, 1992

    1992

  53. [61]

    Iterative algorithms for nonlinear operators

    Xu, H.-K. Iterative algorithms for nonlinear operators. Journal of the London Mathematical Society, 66 0 (1): 0 240--256, 2002

    2002

  54. [62]

    and Ryu, E

    Yoon, T. and Ryu, E. K. Accelerated algorithms for smooth convex-concave minimax problems with O (1/k^2) rate on squared gradient norm. International Conference on Machine Learning, 2021

    2021

  55. [63]

    and Xie, Q

    Zhang, Z. and Xie, Q. Sharper model-free reinforcement learning for average-reward M arkov decision processes. Conference on Learning Theory, 2023

    2023

  56. [64]

    and Chen, Y

    Zurek, M. and Chen, Y. Span-based optimal sample complexity for weakly communicating and general average reward MDP s. Neural Information Processing Systems, 2024

    2024

  57. [65]

    write newline

    " write newline "" before.all 'output.state := FUNCTION n.dashify 't := "" t empty not t #1 #1 substring "-" = t #1 #2 substring "--" = not "--" * t #2 global.max substring 't := t #1 #1 substring "-" = "-" * t #2 global.max substring 't := while if t #1 #1 substring * t #2 gl...

Pith tools

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