We have a game with infinite but countable rounds. We have one machine, that may either break down, or continue operating. For each round the machine operates, it gives cost $-1$ (so profit of $1$). However, it may break down with probability $0.1$ at each round. Our control policy is:

Whenever the machine breaks down pay $c\cdot p^2$ where $c > 0$ is a cost parameter, while $p$ is a variable. The selection of $0 \leq p \leq 1$ gives the probability that repairing the machine will be successful and the machine will operate next round.

So there are two states for the machine: operating, out-of-order (states $O$ and $D$, respectively). My goal is to find out $p$ to minimize my $\alpha$-discounted infinite time horizon cost (we can assume initial state is $O$).


Whenever we are in state $O$, we pay $-1$ cost and go to the $\alpha$-discounted next stage. However, with probability $0.1$ this stage is break-down state, and with $0.9$ probability this is the operating state.

Whenever we are in state $D$, we pay $c\cdot p^2$ and go to the $\alpha$-discounted next stage. This stage will be in state $O$ with probability $p$ and will be $D$ with probability $1-p$.

So the Bellman equations are thus: \begin{align} & V(O) = -1 + \alpha \left[ 0.1 V(D) + 0.9 V(O) \right] \\ & V(D) = c\cdot p^2 + \alpha \left[ (p )V(O) + (1-p) V(D)\right] \end{align} What I do is I re-write the second equation as $V(D) = \text{a function of } V(O)$ and replace this function in the first equation whenever I see $V(D)$. Then, the final expression of $V(O)$ is just a function of $p$: \begin{align} V(O) = \frac{-1 + \alpha - \alpha p + 0.1\alpha cp^2}{(1 - 1.9\alpha + 0.9\alpha^2) + \alpha p - \alpha^2 p} \end{align} I think I should just minimize the above function with respect to $p$. My issues here are:

  1. The second derivative $\geq 0$ is required for convexity (for the usage of FOCs), and the second derivative is massive. I think I also need to constrain $ p \in [0,1]$ so the KKT system is too complicated.
  2. I used a reformulation technique to obtain a convex minimization problem with linear constraint as in here, again it is too complicated and I am afraid if there is some easier way to find the optimal $p$.

1 Answer 1

  1. Note that $V(O)$ is simply of the form $\sf Q_1/L_1$ where $\sf Q_1$ is a quadratic and $\sf L_1$ is a linear function of $p$. This can be written as ${\sf{L_2}}+c/\sf{L_1}$ where $\sf L_2$ is also linear in $p$ and $c$ is a constant. Letting ${\sf L_1}:=mp+n$, the second derivative becomes $$V''(O)=c[(mp+n)^{-1}]''=-cm[(mp+n)^{-2}]'=\frac{2cm^2}{(mp+n)^3}$$ which is $\ge0$ if $c(mp+n)\ge0$. Matching the values of $c,m,n$ is straightforward.

Experiment here. It seems $V''(O)\ge0$ whenever $\alpha\ge10/9$ for all $p\in[0,1]$.

  • $\begingroup$ Thanks for your answer! I am now checking the algebra you suggest. By the way, do you think my optimization over u approach is correct? $\endgroup$ Commented Mar 25, 2020 at 20:11
  • 1
    $\begingroup$ Unfortunately I lack the expertise to comment on your previous steps on the Bellman equations, but the approach for minimisation seems sensible. Maybe someone can chime in on this. $\endgroup$
    – TheSimpliFire
    Commented Mar 25, 2020 at 20:14
  • $\begingroup$ Thanks for that. How can I come with $L_2$? Is there an easy way to apply this split? $\endgroup$ Commented Mar 25, 2020 at 20:24
  • 1
    $\begingroup$ It's a bit messy, but here you go: \begin{align}\frac{ap^2+bp+c}{dp+e}&=\frac ad\frac{p^2+\frac bap+\frac ca}{p+\frac ed}=\frac ad\frac{p^2+\frac edp+\left(\frac ba-\frac ed\right)p+\frac ca}{p+\frac ed}\\&=\frac ad\left(p+\frac{\left(\frac ba-\frac ed\right)p+\frac ca}{p+\frac ed}\right)=\frac adp+\frac ad\left(\frac ba-\frac ed\right)\frac{p+\frac{c/a}{b/a-e/d}}{p+\frac ed}\\&=\underbrace{\frac adp+\frac{bd-ae}{d^2}}_{\sf L_2}+\frac{c-\frac{e(bd-ae)}{d^2}}{dp+e}\end{align} $\endgroup$
    – TheSimpliFire
    Commented Mar 25, 2020 at 20:30
  • 1
    $\begingroup$ Then I take it that $x$ would be a scalar, in which case you will need to ensure that $-\alpha (0.1) c\cdot p^2 + 1 - \alpha +\alpha p$ is a perfect square of a linear function... $\endgroup$
    – TheSimpliFire
    Commented Mar 25, 2020 at 20:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.