Undiscounted Semi-Markov Decision Processes with Countably Infinite Action Spaces
Algorithms · 30.06.2026 · 19 (7) · 529
DOI: 10.3390/a19070529 ↗Kurz gefasst
Fachartikel in der Zeitschrift Algorithms, online erschienen am 30.06.2026. Verfasst von Kushal Guha Bakshi und 4 weiteren Autor:innen. Die Arbeit nennt 27 Literaturangaben. Der Volltext ist frei zugänglich (Open Access, CC BY 4.0).
Abstract (Originalsprache)
In this article, we study semi-Markov decision processes (SMDPs) under the limiting ratio average (undiscounted) pay-off criterion, where the state space is finite and the action space of the decision maker is possibly countably infinite. We impose no restriction on the reward function. We prove that the value of such an SMDP exists and that the decision maker possesses a near-optimal (ϵN-optimal) deterministic (pure) semi-stationary strategy, and we give a truncation-based algorithm that computes the value and such a strategy in finite time by solving a finite linear program at each truncation level. We analyze the algorithm’s computational complexity, showing that each truncation level is solved in time polynomial in the number of state–action pairs, while the number of levels required for termination depends on the prescribed accuracy and on the model. We further establish a certified, computable bound on the truncation error under bounded rewards together with standard ergodicity and tail-regularity conditions, yielding a stopping rule that guarantees a prescribed accuracy; we delimit precisely the regime in which such a certificate exists. Numerical experiments, including randomly generated instances, illustrate the algorithm and its computational behavior. Finally, under standard ergodicity conditions, we derive an optimality equation for these SMDP models.
Zitieren
APA
Bakshi, K. G., Sinha, S., Bhardwaj, R., Bhardwaj, P., & Narayan, S. (2026). Undiscounted Semi-Markov Decision Processes with Countably Infinite Action Spaces. Algorithms, 19(7), 529. https://doi.org/10.3390/a19070529
Vancouver
Bakshi KG, Sinha S, Bhardwaj R, Bhardwaj P, Narayan S. Undiscounted Semi-Markov Decision Processes with Countably Infinite Action Spaces. Algorithms. 2026;19(7):529. doi:10.3390/a19070529
BibTeX
@article{Bakshi2026,
author = {Bakshi, Kushal Guha and Sinha, Sagnik and Bhardwaj, Ramakant and Bhardwaj, Purvee and Narayan, Satyendra},
title = {Undiscounted Semi-Markov Decision Processes with Countably Infinite Action Spaces},
journal = {Algorithms},
year = {2026},
volume = {19},
number = {7},
pages = {529},
doi = {10.3390/a19070529}
}
EUVIMED