pith. sign in

arxiv: 2606.05110 · v1 · pith:HL4VCMZNnew · submitted 2026-06-03 · 💻 cs.DS

Randomization for Faster Exact Optimization of Discounted Markov Decision Processes

Andrei Graur , Aaron Sidford , Ta-Wei Tu This is my paper

Pith reviewed 2026-06-28 03:27 UTC · model grok-4.3

classification 💻 cs.DS
keywords discounted Markov decision processesexact optimizationrandomized algorithmspolicy evaluationapproximate solvingreinforcement learningdeterministic reductions
0
0 comments X

The pith

Efficient reductions from exact DMDP solving to policy evaluation and approximate solving produce faster deterministic and randomized exact algorithms.

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

The paper shows that exact computation of optimal values and policies in discounted Markov decision processes can be reduced to the easier tasks of policy evaluation and approximate value computation. It supplies both a direct deterministic reduction and a randomized variant that improves efficiency. When these reductions are combined with any advance in approximate DMDP methods, the resulting exact algorithms run strictly faster than earlier exact methods. The approach matters because DMDPs underlie planning and reinforcement learning, where exact solutions have historically been limited by slower direct techniques.

Core claim

We obtain faster algorithms for exactly computing optimal values and policies in discounted MDPs by reducing these tasks to policy evaluation and to computing approximately optimal values. We give both a deterministic reduction and a more efficient randomized reduction. Together with existing or future advances in approximate DMDP solvers, these reductions produce strictly faster exact algorithms than previous methods.

What carries the argument

The reductions (deterministic and randomized) that map exact DMDP optimization to policy evaluation and approximate DMDP optimization.

Load-bearing premise

The reductions must be efficient enough that, when paired with approximate DMDP solvers, they produce exact algorithms strictly faster than all prior exact methods.

What would settle it

A concrete DMDP instance family where the running time of the new exact algorithm remains no better than the best prior exact algorithm even after substituting the fastest known approximate solver into the reduction.

read the original abstract

We provide faster deterministic and randomized algorithms for exactly solving discounted Markov Decision Processes (DMDPs). We obtain our results by efficiently reducing computing optimal values and policies in DMDPs to the easier tasks of policy evaluation and computing approximately optimal values in DMDPs. We provide both a straightforward deterministic reduction and a more efficient randomized variant that, together with advances in approximately solving DMDPs, yield our results.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

0 major / 2 minor

Summary. The manuscript claims to deliver faster deterministic and randomized algorithms for exactly solving discounted Markov Decision Processes (DMDPs) by means of efficient reductions from exact value/policy computation to the tasks of policy evaluation and approximate DMDP solving; both a basic deterministic reduction and a more efficient randomized variant are presented, with the overall improvement conditional on pairing the reductions with existing or future advances in approximate DMDP solvers.

Significance. If the claimed reductions are asymptotically efficient and correct, the work supplies a modular route by which progress on approximate DMDP algorithms can be converted into strictly faster exact algorithms, a useful contribution to the algorithmic theory of MDPs. No machine-checked proofs, reproducible code, or parameter-free derivations are described.

minor comments (2)
  1. The abstract and introduction should include explicit big-O runtime expressions for the reductions (both deterministic and randomized) together with a direct comparison table against the best prior exact DMDP algorithms.
  2. Notation for the discount factor, state/action spaces, and approximation parameter should be introduced once in a dedicated preliminaries section and used consistently thereafter.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for the positive summary, the assessment of significance, and the recommendation of minor revision. No major comments were listed in the report.

Circularity Check

0 steps flagged

No significant circularity

full rationale

The paper's central contribution is an algorithmic reduction from exact DMDP solving to the subroutines of policy evaluation and approximate DMDP solving. This reduction is presented as a constructive transformation whose efficiency is analyzed directly in terms of the complexity of the target subroutines; the final runtime claims are explicitly conditional on external or future improvements to those subroutines rather than being derived from quantities fitted or defined inside the paper itself. No self-definitional step, fitted-input prediction, or load-bearing self-citation chain appears in the abstract or the described derivation. The approach is therefore self-contained against external benchmarks and receives the default non-circularity finding.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

Abstract-only review yields minimal ledger. No free parameters, invented entities, or ad-hoc axioms are visible. Relies on standard MDP contraction properties and the existence of prior approximate solvers.

axioms (1)
  • domain assumption Discounted MDPs satisfy the contraction mapping property under the Bellman operator, enabling value iteration convergence.
    Implicit background fact required for any DMDP algorithm to be well-defined.

pith-pipeline@v0.9.1-grok · 5582 in / 1138 out tokens · 34278 ms · 2026-06-28T03:27:25.232147+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

35 extracted references · 3 canonical work pages · 1 internal anchor

  1. [1]

    More asymmetry yields faster matrix multiplication

    [ADV+25] Josh Alman, Ran Duan, Virginia Vassilevska Williams, Yinzhan Xu, Zixuan Xu, and Renfei Zhou. More asymmetry yields faster matrix multiplication. InProceedings of the 2025 Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2025, pages 2005–2039. SIAM,

    2025

  2. [2]

    More asymmetry yields faster matrix multiplication

    [ADW+25] Josh Alman, Ran Duan, Virginia Vassilevska Williams, Yinzhan Xu, Zixuan Xu, and Renfei Zhou. More asymmetry yields faster matrix multiplication. InProceedings of the 2025 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 2005–2039. SIAM,

    2025

  3. [3]

    Kakade, and Lin F

    [AKY20] Alekh Agarwal, Sham M. Kakade, and Lin F. Yang. Model-based reinforcement learn- ing with a generative model is minimax optimal. InConference on Learning Theory, COLT 2020, volume 125 ofProceedings of Machine Learning Research, pages 67–83. PMLR,

    2020

  4. [4]

    On the sample com- plexity of reinforcement learning with a generative model

    [AMK12] Mohammad Gheshlaghi Azar, R´ emi Munos, and Bert Kappen. On the sample com- plexity of reinforcement learning with a generative model. InProceedings of the 29th International Conference on Machine Learning, ICML 2012,

    2012

  5. [5]

    Leffler, Lihong Li, Michael L

    [BLL+09] Emma Brunskill, Bethany R. Leffler, Lihong Li, Michael L. Littman, and Nicholas Roy. Provably efficient learning with typed parametric models.J. Mach. Learn. Res., 10:1955–1988,

    1955

  6. [6]

    Neuro-dynamic programming: an overview

    [BT95] Dimitri P Bertsekas and John N Tsitsiklis. Neuro-dynamic programming: an overview. InProceedings of 1995 34th IEEE conference on decision and control, volume 1, pages 560–564. IEEE,

    1995

  7. [7]

    Cohen, Yin Tat Lee, and Zhao Song

    17 [CLS19] Michael B. Cohen, Yin Tat Lee, and Zhao Song. Solving linear programs in the current matrix multiplication time. InProceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, STOC 2019, pages 938–942. ACM,

    2019

  8. [8]

    [DHNV20] Daniel Dadush, Sophie Huiberts, Bento Natura, and L´ aszl´ o A. V´ egh. A scaling- invariant algorithm for linear programming whose running time depends only on the constraint matrix. InProceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, STOC 2020, pages 761–774. ACM,

    2020

  9. [9]

    [DKN+24] Daniel Dadush, Zhuan Khye Koh, Bento Natura, Neil Olver, and L´ aszl´ o A. V´ egh. A strongly polynomial algorithm for linear programs with at most two nonzero entries per row or column. InProceedings of the 56th Annual ACM Symposium on Theory of Computing, STOC 2024, pages 1561–1572. ACM,

    2024

  10. [10]

    [DNV20] Daniel Dadush, Bento Natura, and L´ aszl´ o A. V´ egh. Revisiting Tardos’s framework for linear programming: Faster exact solutions using approximate solvers. In61st IEEE Annual Symposium on Foundations of Computer Science, FOCS 2020, pages 931–942. IEEE,

    2020

  11. [11]

    Learning the structure of factored markov decision processes in reinforcement learning problems

    [DSW06] Thomas Degris, Olivier Sigaud, and Pierre-Henri Wuillemin. Learning the structure of factored markov decision processes in reinforcement learning problems. InMachine Learning, Proceedings of the Twenty-Third International Conference (ICML 2006), volume 148 ofACM International Conference Proceeding Series, pages 257–264. ACM,

    2006

  12. [12]

    Subexponential lower bounds for randomized pivoting rules for the simplex algorithm

    [FHZ11] Oliver Friedmann, Thomas Dueholm Hansen, and Uri Zwick. Subexponential lower bounds for randomized pivoting rules for the simplex algorithm. InProceedings of the 43rd ACM Symposium on Theory of Computing, STOC 2011, pages 283–292. ACM,

    2011

  13. [13]

    Faster rectangular matrix multiplication by combination loss analy- sis

    [Gal24] Fran¸ cois Le Gall. Faster rectangular matrix multiplication by combination loss analy- sis. InProceedings of the 2024 annual ACM-SIAM symposium on discrete algorithms (SODA), pages 3765–3791. SIAM,

    2024

  14. [14]

    The bit complexity of effi- cient continuous optimization

    [GPV23] Mehrdad Ghadiri, Richard Peng, and Santosh S Vempala. The bit complexity of effi- cient continuous optimization. In2023 IEEE 64th Annual Symposium on Foundations of Computer Science (FOCS), pages 2059–2070. IEEE,

    2059

  15. [15]

    Dantzig’s pivoting rule for shortest paths, deterministic MDPs, and minimum cost to time ratio cycles

    [HKZ14] Thomas Dueholm Hansen, Haim Kaplan, and Uri Zwick. Dantzig’s pivoting rule for shortest paths, deterministic MDPs, and minimum cost to time ratio cycles. InPro- ceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2014, pages 847–860. SIAM,

    2014

  16. [16]

    Truncated variance reduced value iteration

    [JKSW24] Yujia Jin, Ishani Karmarkar, Aaron Sidford, and Jiayi Wang. Truncated variance reduced value iteration. InAdvances in Neural Information Processing Systems 38: Annual Conference on Neural Information Processing Systems 2024, NeurIPS 2024,

    2024

  17. [17]

    Reusing samples in variance reduction.arXiv preprint arXiv:2509.02526,

    [JKSW25] Yujia Jin, Ishani Karmarkar, Aaron Sidford, and Jiayi Wang. Reusing samples in variance reduction.arXiv preprint arXiv:2509.02526,

    work page arXiv

  18. [18]

    Efficiently solving MDPs with stochastic mirror descent

    [JS20] Yujia Jin and Aaron Sidford. Efficiently solving MDPs with stochastic mirror descent. InProceedings of the 37th International Conference on Machine Learning, ICML 2020, volume 119 ofProceedings of Machine Learning Research, pages 4890–4900. PMLR,

    2020

  19. [19]

    A faster algorithm for solving general LPs

    [JSWZ21] Shunhua Jiang, Zhao Song, Omri Weinstein, and Hengjie Zhang. A faster algorithm for solving general LPs. InProceeding of the 53rd Annual ACM SIGACT Symposium on Theory of Computing, STOC 2021, pages 823–832. ACM,

    2021

  20. [20]

    Improved strongly polynomial algorithms for deterministic MDPs, 2VPI feasibility, and discounted all-pairs shortest paths

    [Kar22] Adam Karczmarz. Improved strongly polynomial algorithms for deterministic MDPs, 2VPI feasibility, and discounted all-pairs shortest paths. InProceedings of the 2022 ACM-SIAM Symposium on Discrete Algorithms, SODA 2022, pages 154–172. SIAM,

    2022

  21. [21]

    Kelner and Daniel A

    [KS06] Jonathan A. Kelner and Daniel A. Spielman. A randomized polynomial-time simplex algorithm for linear programming. InProceedings of the 38th Annual ACM Symposium on Theory of Computing, STOC 2006, pages 51–60. ACM,

    2006

  22. [22]

    PAC bounds for discounted MDPs

    [LH12] Tor Lattimore and Marcus Hutter. PAC bounds for discounted MDPs. InAlgorithmic Learning Theory - 23rd International Conference, ALT 2012, volume 7568 ofLecture Notes in Computer Science, pages 320–334. Springer,

    2012

  23. [23]

    Path finding methods for linear programming: Solving linear programs in ˜O( √ rank) iterations and faster algorithms for maximum flow

    [LS14] Yin Tat Lee and Aaron Sidford. Path finding methods for linear programming: Solving linear programs in ˜O( √ rank) iterations and faster algorithms for maximum flow. In 55th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2014, Philadelphia, PA, USA, October 18-21, 2014, pages 424–433. IEEE Computer Society,

    2014

  24. [24]

    Efficient inverse maintenance and faster algorithms for linear programming

    19 [LS15] Yin Tat Lee and Aaron Sidford. Efficient inverse maintenance and faster algorithms for linear programming. In56th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2015, pages 230–249. IEEE Computer Society,

    2015

  25. [25]

    Discounted deterministic markov deci- sion processes and discounted all-pairs shortest paths

    [MTZ09] Omid Madani, Mikkel Thorup, and Uri Zwick. Discounted deterministic markov deci- sion processes and discounted all-pairs shortest paths. InProceedings of the Twentieth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2009, pages 958–967. SIAM,

    2009

  26. [26]

    The simplex method is strongly polynomial for deterministic markov decision processes

    [PY13] Ian Post and Yinyu Ye. The simplex method is strongly polynomial for deterministic markov decision processes. InProceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2013, pages 1465–1473. SIAM,

    2013

  27. [27]

    Oracle-efficient regret minimization in fac- tored MDPs with unknown structure

    [RM21] Aviv Rosenberg and Yishay Mansour. Oracle-efficient regret minimization in fac- tored MDPs with unknown structure. InAdvances in Neural Information Process- ing Systems 34: Annual Conference on Neural Information Processing Systems 2021, NeurIPS 2021, pages 11148–11159,

    2021

  28. [28]

    Improved and generalized upper bounds on the complexity of policy iteration

    [Sch13] Bruno Scherrer. Improved and generalized upper bounds on the complexity of policy iteration. InAdvances in Neural Information Processing Systems 26: 27th Annual Conference on Neural Information Processing Systems 2013., pages 386–394,

    2013

  29. [29]

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

    [SWW+18] Aaron Sidford, Mengdi Wang, Xian Wu, Lin Yang, and Yinyu Ye. Near-optimal time and sample complexities for solving markov decision processes with a generative model. InAdvances in Neural Information Processing Systems 31: Annual Conference on Neural Information Processing Systems 2018, NeurIPS 2018, pages 5192–5202,

    2018

  30. [30]

    A deterministic linear program solver in current matrix multiplica- tion time

    [vdB20] Jan van den Brand. A deterministic linear program solver in current matrix multiplica- tion time. InProceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms, SODA 2020, pages 259–278. SIAM,

    2020

  31. [31]

    Liu, Thatchaphol Saranurak, Aaron Sidford, Zhao Song, and Di Wang

    [vdBLL+21] Jan van den Brand, Yin Tat Lee, Yang P. Liu, Thatchaphol Saranurak, Aaron Sidford, Zhao Song, and Di Wang. Minimum cost flows, MDPs, andℓ 1-regression in nearly linear time for dense instances. InProceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing, STOC 2021, pages 859–869. ACM,

    2021

  32. [32]

    New bounds for matrix multiplication: from alpha to omega

    [VXXZ24] Virginia Vassilevska Williams, Yinzhan Xu, Zixuan Xu, and Renfei Zhou. New bounds for matrix multiplication: from alpha to omega. InProceedings of the 2024 ACM- SIAM Symposium on Discrete Algorithms, SODA 2024, pages 3792–3835. SIAM,

    2024

  33. [33]

    Jia Wan, Sean R

    [Wai19] Martin J. Wainwright. Variance-reduced Q-learning is minimax optimal.CoRR, abs/1906.04697,

    work page arXiv 1906

  34. [34]

    Randomized Linear Programming Solves the Discounted Markov Decision Problem In Nearly-Linear (Sometimes Sublinear) Running Time

    [Wan17] Mengdi Wang. Randomized linear programming solves the discounted markov decision problem in nearly-linear running time.CoRR, abs/1704.01869,

    work page internal anchor Pith review Pith/arXiv arXiv

  35. [35]

    Reinforcement learning in factored MDPs: Oracle- efficient algorithms and tighter regret bounds for the non-episodic setting

    [XT20] Ziping Xu and Ambuj Tewari. Reinforcement learning in factored MDPs: Oracle- efficient algorithms and tighter regret bounds for the non-episodic setting. InAd- vances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, NeurIPS 2020,

    2020