← All problems
Unverified

Increasing-unbounded Simple Components

A one-counter MDP (OC-MDP) MM 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) σ\sigma on MM is a function assigning to each state a single action. Applying σ\sigma to MM yields a one-counter Markov chain MσM_\sigma. We call a sub-OC-MDP of NN a simple component of MM if NN is exactly a BSCC of MσM_\sigma for some cMD strategy σ\sigma. Given a simple component NN, let pp be some state of NN and let XX be a random variable encoding the change of the counter of a run on NN initiated in pp and till pp is revisited for the first time. Let E(X) denote the expected value of XX. We define the following (note it can be shown these are invariant to the choice of pp): NN is bounded if P(X=E(X))=1P(X=E(X))=1, NN is unbounded if P(X=E(X))<1P(X=E(X))<1. and: NN is increasing if E(X)>0E(X)>0, NN is zero if E(X)=0E(X)=0, NN is decreasing if E(X)<0E(X)<0. 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 MM, what is the complexity of deciding whether MM 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 RR of transitions such that NN is zero-bounded iff NN contains only transitions from RR). Bonus problem (very difficult): is it decidable in PTIME whether a given OC-MDP contains a simple component with P(X<0)=0P(X<0)=0?

Coming soon

Organizer

Boyuan Wang portraitBoyuan Wang
Minghan Wang portraitMinghan Wang
Bochao Li portraitBochao Li
Hongwei Hu portraitHongwei Hu