A machine is run week after week with no planned end. Each week its operator decides whether to keep running it or to pay for an overhaul. There is no last stage from which to start a backward recursion, and the total cost over an unbounded future is infinite for every sensible policy, so “minimize the total cost” does not even pose a question.

Two changes rescue the problem. The first is to discount: a cost incurred \(k\) weeks from now is multiplied by \(\alpha^{k}\) for a fixed \(\alpha\) strictly between \(0\) and \(1\) , so that the infinite sum converges. The second is a change of viewpoint. With a finite horizon the unknowns were \(N+1\) functions \(J_0,\dots,J_N\) linked by a recursion. With an infinite horizon and a model that does not change with time, the problem looks the same from every stage, so there is a single unknown function \(J^\star\) , and the recursion turns into an equation that \(J^\star\) must satisfy. This chapter proves that the equation has exactly one solution, that the solution is the optimal cost, and that an optimal policy can be read from it and uses the same rule at every stage. The whole argument rests on one inequality, the contraction property, which is why the discount factor matters so much.

4.1 A model with no last stage

This is the transition-probability form of the model of Chapter 1, with nothing depending on the stage. A function on \(S\) is a vector in \(\mathbb R^{n}\) , and inequalities between such vectors are meant componentwise. Under a stationary policy the state is a Markov chain with transition matrix \(P_\mu\) , whose entry in row \(i\) and column \(j\) is \(p_{ij}(\mu(i))\) ; the \(k\) -step transition probabilities of that chain are the entries of \(P_\mu^{k}\) , a fact from Stochastic Processes used below without further comment.

The limit in the definition exists. Let \(M=\max_{i,u}\lvert g(i,u)\rvert\) . The \(k\) -th term of the sum is at most \(\alpha^{k}M\) in absolute value, so the series converges absolutely and

The second bound says that the infinite-horizon cost differs from the \(N\) -stage cost by a tail that shrinks geometrically. All of the convergence in this chapter comes from that one fact.

4.2 Two operators

The finite-horizon recursion, written in the discounted form of Exercise 2.13, applies the same transformation at every stage. Give the transformation a name.

\((T_\mu J)(i)\) is the cost of a one-stage problem from state \(i\) in which \(\mu\) is used and a terminal cost \(\alpha J\) is charged at the next state; \((TJ)(i)\) is the optimal cost of that one-stage problem. In vector form \(T_\mu J=g_\mu+\alpha P_\mu J\) , an affine map. The operator \(T\) is not affine, because of the minimum, and that is the source of every difficulty that the next chapter’s algorithms have to deal with.

Applying the operators repeatedly builds longer horizons. By Lemma 2.1, \(T_{\mu_0}T_{\mu_1}\cdots T_{\mu_{N-1}}J\) is the cost of using \(\mu_0,\dots,\mu_{N-1}\) over \(N\) stages with terminal cost \(\alpha^{N}J\) ; and by Theorem 2.2, \(T^{N}J\) is the optimal cost of the \(N\) -stage problem with that terminal cost. In particular \(T^{N}0\) is the optimal \(N\) -stage discounted cost.

4.3 The contraction property

Measure the distance between two functions on \(S\) by the maximum norm \(\lVert J\rVert=\max_i\lvert J(i)\rvert\) .

4.4 Bellman’s equation

The theorem turns an optimization over infinitely many policies into \(n\) equations in \(n\) unknowns. It also gives a test that needs no algorithm: to prove a guessed policy optimal, compute its cost by solving a linear system and check whether that cost satisfies Bellman’s equation.

4.5 What the discount factor does

The discount factor is a statement about patience, and the optimal policy depends on it.

Example 4.4: Patience changes the policy

Solve the machine of Example 4.1 for a general \(\alpha\) . Under “never overhaul”, \(J(2)=\dfrac{2}{1-\alpha}\) . Under “overhaul when worn”, eliminating \(J(1)=\dfrac{0.3\alpha J(2)}{1-0.7\alpha}\) from \(J(2)=5+\alpha J(1)\) gives

\[ J(2)=\frac{5\,(10-7\alpha)}{(1-\alpha)(10+3\alpha)} . \]

Overhauling is the better policy when this is the smaller of the two, that is, when \(5(10-7\alpha)\le2(10+3\alpha)\) , or \(\alpha\ge\tfrac{30}{41}\approx0.732\) . A decision maker with \(\alpha\) below \(\tfrac{30}{41}\) prefers to pay \(2\) every week for ever; one with \(\alpha\) above it pays \(5\) now for cheaper weeks later. At \(\alpha=0.5\) the costs from the worn state are \(4\) against \(\tfrac{130}{23}\approx5.652\) ; at \(\alpha=0.9\) they are \(20\) against \(14.567\) .

Multiplying by \(1-\alpha\) , as in the figure, converts a discounted total into a weighted average cost per stage, which makes different discount factors comparable. As \(\alpha\to1\) the normalized cost of the overhaul policy tends to \(\tfrac{15}{13}\) , its long-run average cost per week.

There is a second reading of \(\alpha\) that involves no impatience at all.

Proposition 4.7 (discounting as random termination). Suppose that after each stage the process is terminated with probability \(1-\alpha\) , independently of the states and controls, and that no cost is incurred after termination. Then for every policy the expected total undiscounted cost up to termination equals the discounted cost \(J_\pi(i)\) .

Proof. Stage \(k\) is reached if and only if the process survives \(k\) times, which has probability \(\alpha^{k}\) and is independent of the state and control at stage \(k\) . The expected cost contributed by stage \(k\) is therefore \(\alpha^{k}E[g(x_k,\mu_k(x_k))]\) , and summing over \(k\) gives \(J_\pi(i)\) .

So a machine that is scrapped each week with probability \(0.1\) for outside reasons, and whose owner does not discount at all, is governed by the model with \(\alpha=0.9\) . The expected remaining lifetime is \(\dfrac{1}{1-\alpha}\) stages, which gives a rule of thumb: a discount factor \(\alpha\) means an effective horizon of about \(\dfrac{1}{1-\alpha}\) stages.

4.6 The edge of the theory

Everything above used \(\alpha\) strictly less than \(1\) , a finite state set, and bounded costs. It is worth seeing what each protects against.

If \(\alpha=1\) the operator \(T\) still makes sense, but Lemma 4.3 now says \(T(J+c\mathbf 1)=TJ+c\mathbf 1\) , so \(T\) does not shrink distances and Bellman’s equation can lose uniqueness. In a model with all costs equal to zero, every constant function solves \(J=TJ\) . In the machine example with \(\alpha=1\) every policy has infinite cost from every state, and the criterion no longer separates good policies from bad ones. Undiscounted problems need different tools: an absorbing cost-free state that every policy eventually reaches, which is the setting of the shortest-path problems of Chapter 3, or a criterion of average cost per stage, hinted at by the normalization in Figure 4.1. Neither is developed in this book.

With infinitely many states the same theorems hold for bounded costs, with suprema in place of maxima; with unbounded costs, as in the linear-quadratic problem, the contraction argument is not available and each problem needs its own analysis, as in Theorem 3.6.

Theorem 4.6 says what the optimal cost is. It does not say how to compute it, since \(J=TJ\) is a nonlinear system. Example 4.2 already contains one method, iterating \(T\) , and Example 4.3 contains the germ of another, improving a policy by testing it. Chapter 5 develops both into algorithms and compares them.

Exercises

1. Write the definitions of \(T_\mu\) and \(T\) , state which of the two is an affine map of \(J\) , and say what the fixed point of each one is.

   Answer

   \((T_\mu J)(i)=g(i,\mu(i))+\alpha\sum_jp_{ij}(\mu(i))J(j)\) and \((TJ)(i)=\min_{u\in U(i)}[g(i,u)+\alpha\sum_jp_{ij}(u)J(j)]\) . \(T_\mu\) is affine, \(T_\mu J=g_\mu+\alpha P_\mu J\) ; \(T\) is not, because of the minimum. The fixed point of \(T_\mu\) is the cost \(J_\mu\) of the stationary policy \(\mu\) ; the fixed point of \(T\) is the optimal cost \(J^\star\) .

2. For the machine of Example 4.1 with \(\alpha=0.9\) , compute \(TJ\) for \(J=(5,10)\) , and name the control that attains the minimum in state \(2\) .

   Answer

   \((TJ)(1)=0.9\,(0.7\cdot5+0.3\cdot10)=5.85\) and \((TJ)(2)=\min\{2+0.9\cdot10,\ 5+0.9\cdot5\}=\min\{11,\ 9.5\}=9.5\) , attained by “overhaul”. So \(TJ=(5.85,\ 9.5)\) .

3. Evaluate both stationary policies of Example 4.1 with \(\alpha=0.5\) by solving the two linear systems, and use the test of Example 4.3 to decide which is optimal.

   Solution

   Never overhaul. \(J(2)=2+\tfrac12J(2)\) gives \(J(2)=4\) . Then \(J(1)=\tfrac12\big(0.7J(1)+0.3\cdot4\big)\) gives \(0.65J(1)=0.6\) , so \(J(1)=\tfrac{12}{13}\) .

   Overhaul when worn. \(J(2)=5+\tfrac12J(1)\) and \(J(1)=\tfrac12\big(0.7J(1)+0.3J(2)\big)\) . Substituting, \(0.65J(1)=0.15\,(5+\tfrac12J(1))=0.75+0.075J(1)\) , so \(J(1)=\tfrac{0.75}{0.575}=\tfrac{30}{23}\) and \(J(2)=5+\tfrac{15}{23}=\tfrac{130}{23}\) .

   Test. For “never overhaul”, in state \(2\) : running costs \(2+\tfrac12\cdot4=4\) and overhauling costs \(5+\tfrac12\cdot\tfrac{12}{13}=\tfrac{71}{13}\approx5.46\) . The minimum is \(4=J(2)\) , attained by running. Bellman’s equation holds in state \(2\) , and it holds in state \(1\) because there is only one control. So \(\big(\tfrac{12}{13},4\big)\) is \(J^\star\) and “never overhaul” is optimal at \(\alpha=\tfrac12\) .

   This agrees with Example 4.4, since \(\tfrac12\) is below the threshold \(\tfrac{30}{41}\) . A decision maker whose effective horizon is two weeks will not pay \(5\) to avoid a weekly cost of \(2\) .

4. Prove the two bounds of Section 4.1: that \(\lvert J_\pi(i)\rvert\le M/(1-\alpha)\) , and that the \(N\) -stage cost of a policy differs from \(J_\pi(i)\) by at most \(\alpha^{N}M/(1-\alpha)\) .

   Solution

   Let \(c_k=E[g(x_k,\mu_k(x_k))]\) be the expected cost at stage \(k\) . Since \(\lvert g(i,u)\rvert\le M\) for all \(i\) and \(u\) , the random variable \(g(x_k,\mu_k(x_k))\) lies in \([-M,M]\) and so does its expectation: \(\lvert c_k\rvert\le M\) .

   The \(N\) -stage cost is \(\sum_{k=0}^{N-1}\alpha^{k}c_k\) . The series \(\sum_k\alpha^{k}c_k\) converges absolutely by comparison with the geometric series \(\sum_k\alpha^{k}M\) , so the limit defining \(J_\pi(i)\) exists, and

   \[ \lvert J_\pi(i)\rvert\le\sum_{k=0}^{\infty}\alpha^{k}M=\frac{M}{1-\alpha}. \]

   The difference between \(J_\pi(i)\) and the \(N\) -stage cost is the tail \(\sum_{k=N}^{\infty}\alpha^{k}c_k\) , whose absolute value is at most \(\sum_{k=N}^{\infty}\alpha^{k}M=\dfrac{\alpha^{N}M}{1-\alpha}\) . Both bounds hold for every policy and every initial state, with the same constant, which is what makes the convergence uniform.

5. Let \(P\) be a transition matrix and \(\alpha\in(0,1)\) . Prove that \(I-\alpha P\) is invertible and that its inverse is \(\sum_{k=0}^{\infty}\alpha^{k}P^{k}\) , and interpret the \((i,j)\) entry of the inverse in terms of the Markov chain.

   Solution

   Every entry of \(P^{k}\) lies in \([0,1]\) , because \(P^{k}\) is a transition matrix. So each entry of the partial sums \(S_m=\sum_{k=0}^{m}\alpha^{k}P^{k}\) is a partial sum of a series dominated by \(\sum_k\alpha^{k}\) , and \(S_m\) converges entrywise to a matrix \(S\) . Multiplying out,

   \[ (I-\alpha P)S_m=I-\alpha^{m+1}P^{m+1}\to I\qquad(m\to\infty), \]

   because the entries of \(\alpha^{m+1}P^{m+1}\) are at most \(\alpha^{m+1}\) . Hence \((I-\alpha P)S=I\) , and similarly \(S(I-\alpha P)=I\) ; so \(I-\alpha P\) is invertible with inverse \(S\) .

   The \((i,j)\) entry of \(P^{k}\) is the probability that the chain started at \(i\) is at \(j\) at time \(k\) . So the \((i,j)\) entry of \(S\) is \(\sum_k\alpha^{k}P(x_k=j\mid x_0=i)\) , the expected discounted number of visits to \(j\) starting from \(i\) . The formula \(J_\mu=(I-\alpha P_\mu)^{-1}g_\mu\) then reads: the cost of a policy is the sum over states of the expected discounted number of visits times the cost per visit.

6. Using the machine of Example 4.1, find two vectors \(J\) and \(J'\) for which \(T(J+J')\ne TJ+TJ'\) , and explain which part of the definition of \(T\) is responsible.

   Hint

   Choose \(J\) and \(J'\) so that different controls are minimizing in state \(2\) . For instance \(J=(0,10)\) makes overhauling attractive and \(J'=(10,0)\) makes running attractive; compute \((TJ)(2)\) , \((TJ')(2)\) , and \((T(J+J'))(2)\) . The minimum of a sum is not the sum of the minima.

7. A student evaluates the policy “never overhaul” in Example 4.1, obtains \(J=(14.595,20)\) , checks that \(J(2)=2+0.9J(2)\) and \(J(1)=0.9(0.7J(1)+0.3J(2))\) , and concludes that “\(J\) satisfies Bellman’s equation, so the policy is optimal”. State precisely which equation the student verified, which one was required, and carry out the required check.

   Solution

   The student verified \(J=T_\mu J\) for the policy \(\mu\) “never overhaul”: in each state the equation uses only the control that \(\mu\) prescribes. By Theorem 4.5 every stationary policy’s cost satisfies its own such equation, so the check carries no information about optimality.

   What was required is \(J=TJ\) , in which the right-hand side is a minimum over all controls available in the state. In state \(1\) there is one control and nothing more to check. In state \(2\) the two controls give \(2+0.9\cdot20=20\) for running and \(5+0.9\cdot14.595=18.135\) for overhauling. So \((TJ)(2)=18.135\) , which is less than \(J(2)=20\) : Bellman’s equation fails, and the policy is not optimal.

   The failed check is informative. It shows that using “overhaul” once in state \(2\) and then following “never overhaul” already beats the policy, and Chapter 5 turns that observation into the policy improvement step.

8. Consider a model with two states, one control in each, all costs zero, and \(\alpha=1\) . Show that every constant function is a fixed point of \(T\) , and explain which step of the proof of Theorem 4.5 fails.

   Answer

   With zero costs and \(\alpha=1\) , \((TJ)(i)=\sum_jp_{ij}J(j)\) , and for a constant function \(J=c\mathbf 1\) this is \(c\) . So every constant is a fixed point. The failing step is the uniqueness argument: \(\lVert\bar J-J'\rVert\le\alpha\lVert\bar J-J'\rVert\) forces the distance to be zero only when \(\alpha\) is less than \(1\) . The Cauchy estimate also fails, since \(\sum_k\alpha^{k}\) diverges.

9. A contract is cancelled at the end of each month with probability \(0.2\) , independently of everything else, and costs \(3\) in every month in which it is active. Compute the expected total cost in two ways: by summing a series directly, and by Proposition 4.7.

   Answer

   The contract is active in month \(k\) with probability \(0.8^{k}\) , so the expected total cost is \(\sum_{k=0}^{\infty}0.8^{k}\cdot3=\dfrac{3}{1-0.8}=15\) . By Proposition 4.7 this is the discounted cost of a constant stream of \(3\) with \(\alpha=0.8\) , again \(\dfrac{3}{1-\alpha}=15\) .

10. In Example 4.1 let the overhaul cost be \(c\) in place of \(5\) , with \(\alpha=0.9\) . Find all values of \(c\) for which “overhaul when worn” is optimal.

    Solution

    Evaluate “overhaul when worn” with overhaul cost \(c\) . From \(J(1)=0.9\,(0.7J(1)+0.3J(2))\) , \(J(1)=\tfrac{0.27}{0.37}J(2)\) . Then \(J(2)=c+0.9J(1)=c+\tfrac{0.243}{0.37}J(2)\) , so \(J(2)=\tfrac{0.37}{0.127}\,c=\tfrac{370}{127}c\) .

    By Theorem 4.6 this policy is optimal exactly when its cost satisfies Bellman’s equation, and the only state with a choice is state \(2\) . There the policy’s own control gives \(J(2)\) , and the alternative, running, gives \(2+0.9J(2)\) . The condition \(J(2)\le2+0.9J(2)\) is \(J(2)\le20\) , that is,

    \[ \tfrac{370}{127}c\le20,\qquad c\le\tfrac{254}{37}\approx6.865 . \]

    For \(c\) above this value “never overhaul” is optimal, with \(J(2)=20\) ; at the threshold both policies have cost \(20\) from the worn state and both are optimal. With \(c=5\) the condition holds with room to spare, as Example 4.3 found.

11. For a model with \(M=5\) and \(\alpha=0.9\) , how many stages \(N\) guarantee that the optimal \(N\) -stage cost \(T^{N}0\) is within \(0.01\) of \(J^\star\) in every state? Use Theorem 4.5 with the bound \(\lVert J^\star\rVert\le M/(1-\alpha)\) .

    Answer

    \(\lVert T^{N}0-J^\star\rVert\le\alpha^{N}\lVert J^\star\rVert\le0.9^{N}\cdot50\) . This is at most \(0.01\) when \(0.9^{N}\le2\times10^{-4}\) , that is, \(N\ge\dfrac{\log(2\times10^{-4})}{\log 0.9}\approx80.8\) . So \(N=81\) stages suffice.

12. For the shop of Example 4.5 with \(\alpha=\tfrac12\) , compute the cost vector of the policy “order up to one” by solving \(J=T_\mu J\) , and verify that it satisfies Bellman’s equation.

    Solution

    Under “order up to one” the controls are \(1,0,0\) in states \(0,1,2\) , with expected stage costs \(\tfrac52,\tfrac32,1\) and the transition matrix of Exercise 1.4. With \(\alpha=\tfrac12\) the equations \(J=T_\mu J\) are

    \[ J(0)=\tfrac52+\tfrac12\big(\tfrac34J(0)+\tfrac14J(1)\big),\quad J(1)=\tfrac32+\tfrac12\big(\tfrac34J(0)+\tfrac14J(1)\big),\quad J(2)=1+\tfrac12\big(\tfrac14J(0)+\tfrac12J(1)+\tfrac14J(2)\big). \]

    The first two differ only in their constants, so \(J(1)=J(0)-1\) . Then \(J(0)=\tfrac52+\tfrac12\big(J(0)-\tfrac14\big)\) , giving \(J(0)=\tfrac{19}{4}\) and \(J(1)=\tfrac{15}{4}\) . The third gives \(\tfrac78J(2)=1+\tfrac{19}{32}+\tfrac{15}{16}=\tfrac{81}{32}\) , so \(J(2)=\tfrac{81}{28}\) . Thus \(J=\big(\tfrac{19}{4},\tfrac{15}{4},\tfrac{81}{28}\big)\) .

    Now Bellman’s equation. In state \(0\) : ordering nothing costs \(5+\tfrac12J(0)=\tfrac{59}{8}\) ; ordering one costs \(J(0)=\tfrac{19}{4}=4.75\) ; ordering two costs \(3+\tfrac12\big(\tfrac14J(2)+\tfrac12J(1)+\tfrac14J(0)\big)=\tfrac{137}{28}\approx4.893\) . The minimum is \(\tfrac{19}{4}\) , the policy’s own value. In state \(1\) : ordering nothing costs \(J(1)=\tfrac{15}{4}=3.75\) and ordering one costs \(\tfrac{137}{28}-1\approx3.893\) . In state \(2\) there is no choice. Bellman’s equation holds, so “order up to one” is optimal at \(\alpha=\tfrac12\) , consistently with the threshold \(\tfrac23\) of Example 4.5.

13. Prove that if a function \(J\) satisfies \(J\le TJ\) then \(J\le J^\star\) , and that if \(J\ge TJ\) then \(J\ge J^\star\) .

    Solution

    Suppose \(J\le TJ\) . Applying the monotone operator \(T\) to both sides gives \(TJ\le T^{2}J\) , and by induction \(T^{k}J\le T^{k+1}J\) for every \(k\) . So \(J\le TJ\le T^{2}J\le\dots\le T^{k}J\) for every \(k\) . By Theorem 4.5 and Theorem 4.6, \(T^{k}J\to J^\star\) as \(k\to\infty\) , and a limit of vectors each of which is at least \(J\) is at least \(J\) . Hence \(J\le J^\star\) .

    The second statement is proved in the same way with every inequality reversed: \(J\ge TJ\) implies \(T^{k}J\ge T^{k+1}J\) , so \(J\ge T^{k}J\to J^\star\) .

    The result says that \(J^\star\) is the largest function satisfying \(J\le TJ\) and the smallest satisfying \(J\ge TJ\) . The first description is the basis of the linear programming method of Chapter 5; the second gives upper bounds on the optimal cost from any function that the Bellman operator does not increase.

14. Suppose the stage quantities are rewards \(r(i,u)\) to be maximized. Define the corresponding operator with a maximum, prove that it is a contraction with modulus \(\alpha\) in the maximum norm, and relate its fixed point to the \(J^\star\) of the cost problem with \(g=-r\) .

    Hint

    Define \((T^{r}J)(i)=\max_u[r(i,u)+\alpha\sum_jp_{ij}(u)J(j)]\) . Lemma 4.3 holds for it with the same proof, since a maximum of nondecreasing brackets is nondecreasing and is shifted by a common constant; then repeat the proof of Proposition 4.4. For the relation, show that \(T^{r}(-J)=-TJ\) when \(g=-r\) , so the fixed point of \(T^{r}\) is \(-J^\star\) .

15. Let \(P=\begin{pmatrix}0&1\\0&1\end{pmatrix}\) , \(g_\mu=0\) , and \(\alpha=0.9\) . Show that \(T_\mu\) is not a contraction in the Euclidean norm by computing \(\lVert T_\mu J-T_\mu J'\rVert_2\) for \(J=(0,1)\) and \(J'=(0,0)\) , and explain why this does not contradict Proposition 4.4.

    Answer

    \(T_\mu J-T_\mu J'=\alpha P(J-J')=0.9\,(1,1)\) , whose Euclidean norm is \(0.9\sqrt2\approx1.273\) , while \(\lVert J-J'\rVert_2=1\) . Distances grew. Proposition 4.4 is a statement about the maximum norm, in which \(\lVert T_\mu J-T_\mu J'\rVert=0.9\) and \(\lVert J-J'\rVert=1\) . The contraction property depends on the norm; the maximum norm fits because each row of \(P\) is a probability distribution.

16. Suppose the cost of a transition depends also on the next state, as \(g(i,u,j)\) . Show that the theory of this chapter applies with the expected stage cost \(\bar g(i,u)=\sum_jp_{ij}(u)g(i,u,j)\) , and compute \(\bar g(0,2)\) for the shop from the stage cost of Example 1.1.

    Hint

    Write the expected cost of stage \(k\) given \(x_k=i\) and \(u_k=u\) by conditioning on the next state. Only this expectation enters \(J_\pi\) , \(T_\mu\) , and \(T\) . For the shop, the stage cost of Example 1.1 depends on demand, and so on the next state; its expectation for \(x=0\) , \(u=2\) is the entry \(\bar g(0,2)=3\) of the table there.

17. For the policy “overhaul when worn” of Example 4.1, find the stationary distribution of its Markov chain and the long-run average cost per week, and compare the latter with \((1-\alpha)J_\mu(1)\) at \(\alpha=0.9\) and \(\alpha=0.99\) .

    Solution

    Under “overhaul when worn” the transition matrix is \(P=\begin{pmatrix}0.7&0.3\\1&0\end{pmatrix}\) . A stationary distribution \(\pi=(\pi_1,\pi_2)\) satisfies \(\pi P=\pi\) : \(\pi_2=0.3\pi_1\) , and with \(\pi_1+\pi_2=1\) this gives \(\pi=\big(\tfrac{10}{13},\tfrac{3}{13}\big)\) . In the long run the machine is worn, and an overhaul is paid for, in a fraction \(\tfrac{3}{13}\) of the weeks. The long-run average cost per week is \(0\cdot\tfrac{10}{13}+5\cdot\tfrac{3}{13}=\tfrac{15}{13}\approx1.1538\) .

    From Example 4.4, \(J_\mu(1)=\dfrac{15\alpha}{(1-\alpha)(10+3\alpha)}\) , so \((1-\alpha)J_\mu(1)=\dfrac{15\alpha}{10+3\alpha}\) . At \(\alpha=0.9\) this is \(\tfrac{13.5}{12.7}\approx1.0630\) , and at \(\alpha=0.99\) it is \(\tfrac{14.85}{12.97}\approx1.1449\) . As \(\alpha\to1\) it tends to \(\tfrac{15}{13}\) .

    The normalized discounted cost is a weighted average of the expected stage costs with weights \((1-\alpha)\alpha^{k}\) . As \(\alpha\to1\) the weights spread over an ever longer horizon, the influence of the initial state fades, and the average approaches the stationary average. That the chain forgets its starting state is a property of Markov chains taken from Stochastic Processes (math.stochastic-processes.stationary-distribution).

18. Suppose a policy \(\mu\) and a function \(J\) satisfy \(T_\mu J=TJ\) and \(\lVert J-J^\star\rVert\le\varepsilon\) , but \(J\) is not exactly \(J^\star\) . Give an example, using Example 4.2, in which \(\mu\) is not optimal, and explain why this does not contradict Theorem 4.6.

    Hint

    Take \(J=J_2=(0.54,\,3.8)\) from Example 4.2. Which control attains the minimum in \((TJ)(2)\) ? Is that the optimal control? Theorem 4.6 characterizes optimal policies by \(T_\mu J^\star=TJ^\star\) , with the exact optimal cost; a policy that is greedy for an approximation of \(J^\star\) need not be optimal, and Chapter 10 bounds how much it can lose.