Metraipolis › archive › dc_eaa7201b2518

Transformation of Adaptive Multistage Sampling for Solving Finite-Horizon Markov Decision Processes with Unknown Model — arXiv:2609.05856

Source
arXiv (en)
Original
https://arxiv.org/abs/2609.05856
License (as archived)
CC0-1.0
Archived
2026-10-16T14:23:57.666Z
SHA-256 of the archived text
bdbfdad4f279727692661314b83978605f0ebf1b6c0ab5245aa413a80fb57f33
Stable URL of this page
https://metraipolis.com/documento/dc_eaa7201b2518

How to cite

Transformation of Adaptive Multistage Sampling for Solving Finite-Horizon Markov Decision Processes with Unknown Model — arXiv:2609.05856 — arXiv (en), https://arxiv.org/abs/2609.05856 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_eaa7201b2518 (Metraipolis archive dc_eaa7201b2518, sha256 bdbfdad4f279727692661314b83978605f0ebf1b6c0ab5245aa413a80fb57f33)
BibTeX
@misc{dceaa7201b2518,
  title = {Transformation of Adaptive Multistage Sampling for Solving Finite-Horizon Markov Decision Processes with Unknown Model — arXiv:2609.05856},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2609.05856},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_eaa7201b2518; sha256 bdbfdad4f279727692661314b83978605f0ebf1b6c0ab5245aa413a80fb57f33},
  year = {2026}
}

Archived text

Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2609.05856. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

This work provides a learning approach to solving finite-horizon Markov decision processes (MDPs) when the underlying model of a given finite MDP is unknown to the decision maker. We transform the adaptive multistage sampling (AMS) algorithm into a sampling-free algorithm, called "adaptive multistage rollout (AMR)," for estimating the optimal value at an initial state when only the state set and the action set are known. AMR emulates the backward induction as in AMS but in a reinforcement learning (RL) setting. At each iteration, AMR generates a non-stationary policy to be used for exploration and rolls out the policy in order to obtain a single trajectory of experiences and traces it backwards in a non-recursive way while doing relevant updates only at visited states and for actions taken at the visited states. We show that AMR is asymptotically optimal such that the sequence of the expected absolute errors approaches zero and its convergence rate depends on the number of visits to each reachable state at each stage from the initial state, essentially transforming the result of AMS into the RL setting.

Tema degli esploratori: matematica e informatica teorica (retro-catalogo arXiv: annunci del 2026-09-09 in math.OC).
Categorie arXiv: Optimization and Control (math.OC).
Pagina del lavoro: https://arxiv.org/abs/2609.05856 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-10-16T14:09:21.651Z dalla pagina https://arxiv.org/catchup/math.OC/2026-09-09?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).