Increasing-unbounded Simple Components
A one-counter MDP (OC-MDP) is an MDP where each transition is labeled by an integer which is added to the counter whenever the transition is taken. A counterless MD strategy (cMD) on is a function assigning to each state a single action. Applying to yields a one-counter Markov chain . We call a sub-OC-MDP of a simple component of if is exactly a BSCC of for some cMD strategy . Given a simple component , let be some state of and let be a random variable encoding the change of the counter of a run on initiated in and till is revisited for the first time. Let E(X) denote the expected value of . We define the following (note it can be shown these are invariant to the choice of ): is bounded if , is unbounded if . and: is increasing if , is zero if , is decreasing if . For example a simple random walk (+-1 with equal probability) would have a single zero-unbounded simple component. The question is: Given a OC-MDP , what is the complexity of deciding whether contains an increasing-unbounded simple component? What is the complexity of this problem for the subclass of OC-MDPs that contain no decreasing simple components? These are trivially in NP, but can they be solved in PTIME? Alternatively, is there a way to effectively encode all increasing-bounded (or increasing-unbounded) simple components? (for example for the class of OC-MDPs containing no decreasing simple components there exists a set of transitions such that is zero-bounded iff contains only transitions from ). Bonus problem (very difficult): is it decidable in PTIME whether a given OC-MDP contains a simple component with ?
