We study the asymptotics of various types of expected complexity in Vector Addition Systems with States over Markov Decision Processes (VASS MDP). We provide a full classification of the asymptotics of expected termination, counter, and transition complexities in one-counter VASS MDPs, and we show this class can be fully classified in \(\textbf{PTIME}\) . We also show \(\textbf{PSPACE}\) -hardness for multiple problems related to the asymptotics of expected termination and counter complexity in VASS MDPs. Namely, that any non-trivial instance of deciding whether such complexity is in \(\mathcal {O}\big (f(n)\big ) \) or \(\varOmega \big (f(n)\big ) \) is \(\textbf{PSPACE}\) -hard for general VASS MDPs. For the class of strongly connected VASS MDPs we show \(\textbf{PSPACE}\) -hardness for deciding whether such expected complexity is in \(2^{\mathcal {O}\big (f(n)\big )} \) for given \(f\in \varOmega (n) \) , or \(2^{\varOmega \big (f(n)\big )} \) for given \(f\in \omega (n) \) . Finally, we also show that deciding whether such expected complexity for a given VASS MDP is finite is \(\textbf{PSPACE}\) -hard already for the class of strongly connected VASS MDPs.