I think your problem is that you have not specified your model. In your verbal formulation it does not seem even to be a Markov decision model. My proposal is the following formulation: Let
$S := \mathbb{N}_0$ be the state space, $A := [0,M]$ be the action space, endowed with Borel-$\sigma$-algebra $\cal{A}$, $q \colon S \times A \to P(S)$ be a Markov kernel with $P(S)$ be the space of all probabability measures on $S$ with the property that $p(s,a) = \delta_{s-1}$ for $s > 0$. The reward is a bounded (measurable) function $r \colon S \times A \to \mathbb{R}$ (you have punishment) with $r(s,a) \equiv 0$ for all $s > 0$. Then you are in the usual framework of MDP's. The only problem here is that $A$ is not countable. I think this is artificial generality.
Further you always return infinitely often to the state $s = 0$, so your second remark does not apply. Have a look into the book "Controlled Markov Processes" from E.B. Dynkin, A.A. Yushkevich, Springer (1979), ch. 7 or "Markov Decision Processes" of M.L. Puterman, Wiley & Sons (1994), ch.8.
Edit: As usual the problem with such models is: Describes it correctly the original problem? This usually can only be solved together with the user. If my formulation is correct it can be easily solved:
Let $X_a$ be any random variable with $\mathbb{P}(X_a = s) = q(0,a)(\{s\}), s \in S$ for $a \in A$. ($X_a+1$ is the random time until we reach $s = 0$ again, if we choose action $a \in A$). If there is any $a_0 \in A$ with $$\frac{r(0,a)}{\mathbb{E}(X_a+1)} \leq \frac{r(0,a_0)}{\mathbb{E}(X_{a_0}+1)}$$ for any $a \in A$, then it is optimal to choose always action $a_0$ if we are in state $s = 0$. We tentatively assume $\mathbb{E}X_a < \infty$ for all $a \in A$. Of course $a_0$ exists if $A$ is finite. (States $s \not= 0$ here are irrelevant.)