Special subclass of Generalized Semi-Markov Decision Processes with discrete time

EasyChair Preprint 2336, version 2

Abstract

The class of Generalized Semi-Markov Decision Processes (GSMDPs) covers a large area of stochastic modelling. For continuous time steps modelled problems are discussed in some articles, but not for the discrete case. Several events can be triggered in the same time step and the evaluation of them is more complex than for continuous time, if the agreement is made that two events can not be triggered at the same time point.

In this paper a specification for discrete GSMDPs is defined and analysed. The exponential cost, solving these problems more or less exactly, are reduced to a polynomial number by two randomized approaches. Runtimes and relative results, compared to almost exact solutions, are shown and some extensions for the common class of discrete GSMDPs are mentioned.

Keyphrases: Discrete time steps, GSMDP, Graph paths, events, randomized algorithms, stochastic games

@booklet{EasyChair:2336,
  author    = {Alexander Frank},
  title     = {Special subclass of Generalized Semi-Markov Decision Processes with discrete time},
  howpublished = {EasyChair Preprint 2336},
  year      = {EasyChair, 2020}}