Transformation of Adaptive Multistage Sampling for Solving Finite-Horizon Markov Decision Processes with Unknown Model
Abstract
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.
Related
- Extreme Population Selection under Multistage Sampling design With Applications
- K–β Risk-Threshold Optimization for Multistage Adaptive Task Assignment and Recovery of Heterogeneous UAVs
- An approximate zero bias transformation for random sums: Applications to sampling with outliers, auto insurance, and generative AI
- A relationship between three-dimensional Bessel processes in terms of Pitman's transformation
- Worst-Case Bayesian CVaR Regret Bounds for Episodic Markov Decision Processes
BibTeX
@misc{chang2026transformation,
title = {{Transformation of Adaptive Multistage Sampling for Solving Finite-Horizon Markov Decision Processes with Unknown Model}},
author = {Hyeong Soo Chang},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2609.05856},
eprint = {2609.05856},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.05856},
note = {CC0},
}
RIS
TY - UNPB
TI - Transformation of Adaptive Multistage Sampling for Solving Finite-Horizon Markov Decision Processes with Unknown Model
AU - Hyeong Soo Chang
PY - 2026
DA - 2026/10/29
PB - arXiv
DO - 10.48550/arxiv.2609.05856
UR - https://arxiv.org/abs/2609.05856
AB - 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.
ER -