{"ID":3049916,"CreatedAt":"2026-06-04T02:13:16.786527022Z","UpdatedAt":"2026-06-06T15:44:26.945507316Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2606.05110","arxiv_id":"2606.05110","title":"Randomization for Faster Exact Optimization of Discounted Markov Decision Processes","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.","short_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 provid...","url_abs":"https://arxiv.org/abs/2606.05110","url_pdf":"https://arxiv.org/pdf/2606.05110v1","authors":"[\"Andrei Graur\",\"Aaron Sidford\",\"Ta-Wei Tu\"]","published":"2026-06-03T17:11:42Z","proceeding":"cs.DS","tasks":"[\"cs.DS\"]","methods":"[]","has_code":false}