-
A student has two days before an examination. Knowledge is at level \(0\) , \(1\) , or \(2\) ; studying for a day costs \(1\) and raises the level by one with probability \(0.8\) , leaving it unchanged otherwise; resting costs nothing and changes nothing. The examination penalty is \(5\) , \(2\) , or \(0\) at levels \(0\) , \(1\) , \(2\) . Find the policy that minimizes the expected total cost and the optimal cost from level \(0\) .
Solution
Let \(J_k(x)\) be the optimal expected cost from level \(x\) at the start of day \(k\) , with \(J_2=(5,2,0)\) the examination penalty.
Day 1. Level \(0\) : studying costs \(1+0.8\cdot2+0.2\cdot5=3.6\) ; resting costs \(5\) . Study. Level \(1\) : studying costs \(1+0.8\cdot0+0.2\cdot2=1.4\) ; resting costs \(2\) . Study. Level \(2\) : resting costs \(0\) ; studying costs \(1\) . Rest. So \(J_1=(3.6,\ 1.4,\ 0)\) .
Day 0. Level \(0\) : studying costs \(1+0.8\cdot1.4+0.2\cdot3.6=2.84\) ; resting costs \(J_1(0)=3.6\) . Study. Level \(1\) : studying costs \(1+0.8\cdot0+0.2\cdot1.4=1.28\) ; resting costs \(1.4\) . Study. Level \(2\) : rest.
The optimal policy is to study on any day on which the level is below \(2\) , and the optimal cost from level \(0\) is \(2.84\) . Studying is worth its cost here even on the last day because one level is worth \(3\) or \(2\) in penalty and is gained with probability \(0.8\) .
-
In the previous problem suppose that studying on two consecutive days costs \(2\) on the second day in place of \(1\) . Explain why the level is no longer a state, give a state that is, and find the optimal first-day decision and expected cost from level \(0\) .
Solution
The cost of studying on day \(1\) depends on whether the student studied on day \(0\) , which the level does not record: a student at level \(0\) on day \(1\) may have rested, or studied and failed. So the level fails the test of Section 1.3. The pair (level, studied yesterday) is a state.
Day 1 after studying on day 0. Level \(1\) : studying costs \(2+0.2\cdot2=2.4\) ; resting costs \(2\) . Rest, cost \(2\) . Level \(0\) : studying costs \(2+0.8\cdot2+0.2\cdot5=4.6\) ; resting costs \(5\) . Study, cost \(4.6\) .
Day 1 after resting on day 0, at level \(0\) : as in the previous problem, study, cost \(3.6\) .
Day 0 at level 0. Studying costs \(1+0.8\cdot2+0.2\cdot4.6=3.52\) . Resting costs \(3.6\) . Study on day \(0\) ; the expected cost is \(3.52\) . On day \(1\) the student now rests after a success, where before a second day of study was worthwhile, and studies again only after a failure.
-
A graph has nodes \(1,2,3\) and destination \(t\) , with arcs \(1\to2\) of length \(4\) , \(1\to3\) of length \(2\) , \(2\to3\) of length \(2\) , \(3\to2\) of length \(-1\) , \(2\to t\) of length \(3\) , and \(3\to t\) of length \(5\) . Check that no cycle has negative length, compute the shortest distances to \(t\) by successive approximation, and give the shortest path from node \(1\) .
Answer
The only cycle is \(2\to3\to2\) , of length \(2-1=1\) . Successive approximation: \(J_1=(\infty,3,5)\) ; \(J_2=(7,3,2)\) , using \(J_2(3)=\min\{5,\ -1+3\}\) ; \(J_3=(4,3,2)\) , using \(J_3(1)=\min\{4+3,\ 2+2\}\) ; \(J_4=J_3\) . The shortest path from node \(1\) is \(1\to3\to2\to t\) with length \(2-1+3=4\) .
-
A process is in state A or B. In A one may stay, at cost \(1\) , remaining in A, or move, at cost \(2\) , going to B. In B the cost is \(0\) and the next state is A or B with probability \(\tfrac12\) each. With discount factor \(0.8\) , evaluate the policy that always stays, perform one policy improvement step, and decide whether the improved policy is optimal.
Solution
Evaluate “stay”. \(J(A)=1+0.8J(A)\) gives \(J(A)=5\) . \(J(B)=0.8\big(\tfrac12J(A)+\tfrac12J(B)\big)\) gives \(0.6J(B)=2\) , so \(J(B)=\tfrac{10}{3}\) .
Improve. In A: staying costs \(5\) ; moving costs \(2+0.8\cdot\tfrac{10}{3}=\tfrac{14}{3}\approx4.67\) . Moving is smaller, so the improved policy moves.
Evaluate “move”. \(J(A)=2+0.8J(B)\) and \(J(B)=0.4J(A)+0.4J(B)\) , so \(J(B)=\tfrac23J(A)\) and \(J(A)=2+\tfrac{8}{15}J(A)\) , giving \(J(A)=\tfrac{30}{7}\approx4.29\) and \(J(B)=\tfrac{20}{7}\approx2.86\) .
Test. In A: moving costs \(\tfrac{30}{7}\) ; staying costs \(1+0.8\cdot\tfrac{30}{7}=\tfrac{31}{7}\) , which is larger. Bellman’s equation holds, so “move” is optimal. Paying \(2\) to reach a state with no running cost beats paying \(1\) for ever, at this discount factor.
-
Value iteration with discount factor \(0.9\) is stopped at an iterate \(J_k\) for which every component of \(J_k-J_{k-1}\) lies between \(0.02\) and \(0.05\) . Give the tightest interval that is guaranteed to contain \(J^\star(i)\) for each state \(i\) , in terms of \(J_k(i)\) .
Answer
By Proposition 5.2 with \(\tfrac{\alpha}{1-\alpha}=9\) : \(J_k(i)+0.18\le J^\star(i)\le J_k(i)+0.45\) for every state \(i\) .
-
Demand for a product is equally likely to be any whole number from \(1\) to \(10\) . Each unit stocked costs \(2\) , each unit left over costs a further \(1\) , and each unit of unmet demand costs \(6\) . Find the stock level that minimizes the expected cost, and say how the answer would change if demand were known in advance.
Solution
With \(c=2\) , \(h=1\) , \(b=6\) the critical ratio of Theorem 6.5 is \(\dfrac{b-c}{b+h}=\dfrac47\approx0.571\) . The distribution function is \(F(y)=\tfrac{y}{10}\) for \(y=1,\dots,10\) , and the smallest \(y\) with \(F(y)\ge0.571\) is \(y=6\) .
As a check, with \(y=6\) the expected surplus is \(\tfrac{1}{10}(5+4+3+2+1)=1.5\) and the expected shortage is \(\tfrac1{10}(1+2+3+4)=1\) , so the expected cost is \(12+1.5+6=19.5\) . For \(y=5\) it is \(10+1+9=20\) , and for \(y=7\) it is \(14+2.1+3.6=19.7\) .
If demand were known in advance the stock would equal the demand, with no surplus and no shortage, at an expected cost of \(2\cdot5.5=11\) . The value of perfect information is \(19.5-11=8.5\) , which is what uncertainty costs in this problem even under the best stocking rule.
-
A component is faulty with prior probability \(0.3\) . A test reads “fault” with probability \(0.9\) on a faulty component and \(0.2\) on a sound one, and repeated tests are independent given the component’s condition, which does not change. Find the probability of a fault after two tests that both read “fault”, and after one that reads “fault” followed by one that does not.
Answer
Prior odds of a fault are \(\tfrac37\) . A “fault” reading multiplies the odds by \(\tfrac{0.9}{0.2}=4.5\) and a “no fault” reading by \(\tfrac{0.1}{0.8}=0.125\) . After two “fault” readings the odds are \(\tfrac37\cdot20.25\approx8.68\) , a probability of \(0.897\) . After one of each the odds are \(\tfrac37\cdot4.5\cdot0.125\approx0.241\) , a probability of \(0.194\) : the two readings nearly cancel, leaving the belief below the prior because a missed fault is rarer than a false alarm.
-
Offers for an asset are independent and exponentially distributed with mean \(1\) , and at most three offers will be received, the last of which must be accepted. Show that \(E[\max\{w,a\}]=a+e^{-a}\) for \(a\ge0\) , compute the reservation prices, and find the expected sale price.
Solution
For \(a\ge0\) , \(E[\max\{w,a\}]=a+E[\max\{w-a,0\}]=a+\int_a^{\infty}(w-a)e^{-w}\,dw=a+e^{-a}\) , substituting \(s=w-a\) in the integral.
By Theorem 8.2, \(V_0=0\) , \(V_1=0+e^{0}=1\) , \(V_2=1+e^{-1}\approx1.368\) , and \(V_3=V_2+e^{-V_2}\approx1.368+0.255=1.623\) .
The reservation price for the first offer is \(V_2\approx1.368\) ; for the second, \(V_1=1\) ; the third is accepted whatever it is. The expected sale price is \(V_3\approx1.623\) , against \(1\) for accepting the first offer. The first offer is accepted with probability \(e^{-1.368}\approx0.25\) only: with an exponential distribution large offers are possible, and it pays to wait for one.
-
An angler has caught \(x\) fish. Each further cast catches one fish with probability \(\tfrac12\) , but before the cast is completed a warden arrives with probability \(0.1\) and confiscates the entire catch, ending the day. Find the rule that maximizes the expected number of fish taken home, and justify its optimality.
Solution
Stopping with \(x\) fish yields \(x\) . One more cast and then stopping yields \(0.9\,(x+\tfrac12)\) , since with probability \(0.1\) everything is lost and otherwise the expected catch rises by \(\tfrac12\) . Stopping is at least as good when \(x\ge0.9x+0.45\) , that is, \(x\ge4.5\) . The one-step look-ahead set is \(\{x\ge5\}\) .
The set is absorbing: from \(x\ge5\) a further cast leads to \(x\) or \(x+1\) , both in the set, or to confiscation, which ends the day. By Theorem 8.4, for any limit on the number of casts, the rule “fish until five are caught, then go home” is optimal. At \(x=4\) one more cast is worth \(0.9\cdot4.5=4.05\) , slightly more than \(4\) ; at \(x=5\) it is worth \(4.95\) , less than \(5\) .
-
For the scalar system \(x_{k+1}=x_k+2u_k\) with cost \(x_2^{2}+\sum_{k=0}^{1}(x_k^{2}+4u_k^{2})\) , compute the Riccati values \(K_1\) , \(K_0\) and the gains \(L_1\) , \(L_0\) , and give the optimal control sequence from \(x_0=1\) .
Answer
With \(a=1\) , \(b=2\) , \(q=1\) , \(r=4\) : \(K_2=1\) ; \(K_1=1+\dfrac{4\cdot1}{4+4}=1.5\) and \(L_1=\dfrac{2\cdot1}{8}=0.25\) ; \(K_0=1+\dfrac{4\cdot1.5}{4+6}=1.6\) and \(L_0=\dfrac{2\cdot1.5}{10}=0.3\) . From \(x_0=1\) : \(u_0=-0.3\) , \(x_1=0.4\) , \(u_1=-0.1\) , \(x_2=0.2\) . The cost is \(1+0.36+0.16+0.04+0.04=1.6=K_0\) .
-
For \(\dot x=u\) with cost \(\int_0^{\infty}(4x^{2}+u^{2})\,dt\) , find the optimal feedback and the optimal cost from \(x_0\) by solving the stationary Hamilton–Jacobi–Bellman equation with a quadratic trial function, and verify the answer against the algebraic Riccati equation.
Solution
The stationary equation is \(0=\min_u[4x^{2}+u^{2}+V_xu]\) . Try \(V=Kx^{2}\) : the bracket is \(4x^{2}+u^{2}+2Kxu\) , minimized at \(u=-Kx\) with value \((4-K^{2})x^{2}\) . This vanishes for all \(x\) when \(K=2\) , taking the positive root. So \(V=2x^{2}\) , the feedback is \(u=-2x\) , the closed loop is \(\dot x=-2x\) , and the cost from \(x_0\) is \(2x_0^{2}\) .
Check by direct computation: \(x=x_0e^{-2t}\) and \(u=-2x_0e^{-2t}\) give \(\int_0^{\infty}(4+4)x_0^{2}e^{-4t}\,dt=2x_0^{2}\) . The algebraic Riccati equation with \(A=0\) , \(B=1\) , \(Q=4\) , \(R=1\) is \(-K^{2}+4=0\) , the same equation. The trial function \(V\) is smooth and the closed-loop state tends to zero, so the verification argument of Theorem 9.2, applied on \([0,T]\) with terminal function \(V\) and then letting \(T\to\infty\) , confirms optimality among controls that drive the state to zero.
-
A cart obeys \(\dot x_1=x_2\) , \(\dot x_2=u\) with \(\lvert u\rvert\le1\) and starts at rest at \(x_1=-2\) . Find the control that brings it to rest at the origin in minimum time, the switching time, the minimum time, and the costate \(p_2(t)\) normalized so that the Hamiltonian vanishes.
Solution
At \((-2,0)\) the quantity \(x_1+\tfrac12x_2\lvert x_2\rvert\) is negative: the state is to the left of the switching curve, so \(u=+1\) first. Then \(x_2=t\) and \(x_1=-2+\tfrac12t^{2}\) . The arc into the origin under \(u=-1\) is \(x_1=-\tfrac12x_2^{2}\) with \(x_2\ge0\) ; it is met when \(-2+\tfrac12t^{2}=-\tfrac12t^{2}\) , at \(t=\sqrt2\) , in the state \((-1,\sqrt2)\) . Then \(u=-1\) for a further \(\sqrt2\) brings the cart to rest. The minimum time is \(T=2\sqrt2\approx2.83\) , in agreement with the elementary bound \(T\ge2\sqrt{d}\) for a rest-to-rest transfer over distance \(d\) .
Costate. \(p_2\) is linear and vanishes at the switch; \(u=-\operatorname{sgn}p_2=+1\) before it, so \(p_2\) is negative there: \(p_2(t)=c\,(t-\sqrt2)\) with \(c\) positive. At \(t=0\) , \(x_2=0\) and \(u=1\) , so \(H=1+p_2(0)=1-c\sqrt2=0\) , giving \(c=\tfrac1{\sqrt2}\) :
\[ p_2(t)=\frac{t}{\sqrt2}-1,\qquad p_1=-\frac1{\sqrt2}. \] -
For \(\dot x=u\) on \([0,1]\) with \(u\) unconstrained, \(x(0)=0\) , and cost \(\big(x(1)-1\big)^{2}+\tfrac12\int_0^1u^{2}\,dt\) , write the costate equation, the stationarity condition, and the transversality condition, solve them, and give the optimal control, final state, and cost.
Solution
The Hamiltonian is \(H=\tfrac12u^{2}+pu\) . Stationarity: \(u+p=0\) . Costate equation: \(\dot p=-H_x=0\) , so \(p\) is constant. Transversality: \(p(1)=\varphi'(x(1))=2\big(x(1)-1\big)\) .
The control is the constant \(u=-p\) , so \(x(1)=-p\) . Then \(p=2(-p-1)\) gives \(p=-\tfrac23\) . Hence \(u\equiv\tfrac23\) , \(x(1)=\tfrac23\) , and the cost is \(\big(\tfrac23-1\big)^{2}+\tfrac12\cdot\tfrac49=\tfrac19+\tfrac29=\tfrac13\) .
The control moves the state two thirds of the way to the target value \(1\) : going all the way would cost \(\tfrac12\) in control effort, staying put would cost \(1\) in terminal penalty, and the optimum balances the marginal costs, which is what transversality expresses. By Theorem 9.8 the extremal is optimal, since the Hamiltonian and the terminal cost are convex.
-
A discounted problem with \(\alpha=0.95\) has a state space too large for exact solution. An approximation \(\tilde J\) is believed to satisfy \(\lVert\tilde J-J^\star\rVert\le0.05\) . Give the guaranteed bound on the loss of the greedy policy, and describe one way to obtain a lower bound on \(J^\star\) against which the greedy policy’s simulated cost could be compared.
Answer
Theorem 10.1 gives a loss of at most \(\dfrac{2\cdot0.95\cdot0.05}{0.05}=1.9\) in every state. For a lower bound on \(J^\star\) : any function with \(J\le TJ\) lies below \(J^\star\) (Exercise 4.13); alternatively, the expected cost of acting with full knowledge of the future disturbances, computed by solving one deterministic problem per simulated disturbance path, is a lower bound by Section 6.3. If the greedy policy’s simulated cost is close to such a bound, it is close to optimal, whatever the guarantee says.