Lecture 8

You will find that the policy improvement algorithm is useful in answering Questions 3 and 4 on Examples Sheet 2. In Question 3, you will find $\lambda$ and $\phi$ for a certain policy ("On seeing a filling station, stop and fill the tank"), and then look for a condition that the policy improvement algorithm will not improve it (or, equivalently, that this $\lambda$ and $\phi$ satisfy the optimality equation.

In Question 4 you will use policy improvement idea in the context of a discounted-cost problem. You find $F(x)$ for a simple policy (in which the engineer allocates his time randomly), and then improve it by a step of the policy improvement algorithm. This leads to a policy in which the engineer puts all his maintenance effort into the machine with greatest value of $c_i(x_i+q_i)/(1-\beta b_i)$. This policy is better, but may not yet be optimal.

In Question 1 you will want to mimic the calculation done in the proof of Bruss's odds algorithm. You cannot solve this by simply applying the algorithm directly.

There is another interesting way to motivate the optimality equationin the average cost case. This can be made rigorous and helps us understand the relative value function $\phi(x)$.

Let $F(x)$ be the infinite-horizon value function when the discount factor is $\beta$. Then we know this satisfies the optimality equation

$F(x) = \min_u \{ c(x,u) +\beta E[ F(x_1) \mid x_0=x,u_0=u ] \}$ .

Pick some state, say state 0. By subtracting $\beta F(0)$ from both sides of the above, we obtain

$F(x) – F(0) + (1–\beta)F(0) = \min_u \{ c(x,u) + β E[ F(x_1) – F(0) \mid x_0=x,u_0=u ] \}$

One can show that as  $\beta\to 1$ we have have $F(x) – F(0) \to \phi(x)$ and $(1–\beta)F(0) \to\lambda$ (the average-cost). Thus we obtain

$\phi(x) + \lambda = \min_u \{ c(x,u) + E[ \phi(x_1) \mid x_0=x,u_0=u ] \}$ 

and this is our average-cost optimality equation. If you would like to understand why $(1–\beta)F(0) \to\lambda$  see this small note about the connection between the average-cost problem and the discounted-cost problem with $\beta$ near 1.


It is also interesting to think about the following (which I mentioned briefly in lectures today). Suppose we have a deterministic stationary Markov policy, say π, with u=f(x). Suppose we have λ and φ such that

φ(x) + λ = c(x,f(x)) + Σ_y φ(y) P(y | x )     (7.6)

where P(y | x) is the transition matrix under π.
Suppose π induces an ergodic Markov chain (i.e. a Markov chain that is irreducible and positive recurrent) and this has invariant distribution μ. We know that

μ_y = Σ_x μ_x P( y | x)     (7.7)

Multiplying (7.6) through by μ_x and then summing on x, we get

Σ_x μ_x φ(x) + λ Σ_x μ_x

= Σ_x μ_x c(x,f(x)) + Σ_y Σ_x μ_x φ(y) P( y | x)

which, using (7.7) gives

Σ_x μ_x φ(x) + λ Σ_x μ_x = Σ_x μ_x c(x,f(x)) + Σ_y μ_y φ(y).

Then using Σ_x μ_x = 1, and cancelling the terms that are equal on both sides, we have

λ = Σ_x μ_x c(x,f(x))

and so we see that λ is the average-cost of policy π.

Lecture 7

In today's lecture I used a portion of my slides from a talk on the Gittins Index. You may enjoy looking through the entire talk. It will look better if you download the .pdf file to your computer and read the presentation with a .pdf viewer such as acrobat, rather than try to read within your browser.

The proof of the Gittins index theorem is actually easy, but at the same time deep. It is non-examinable. I would expect you only to know what we mean by a SFABP, the statement of the Gittins index theorem, and how to calculate the indices in simple examples. However, I thought you would enjoy seeing this beautiful result and how it can be proved. Lectures 1-6 have covered everything you need to know in order to understand the Gittins index. Today's lecture has also been an opportunity to revise ideas that we already met in problems on job scheduling and pharmaceutical trials. 

Weiztman's Pandora's boxes problem in 7.5 is cute and something I am talking about for the first time. I may have rushed over it a bit, so refer to the notes. I have there an example in which the prize in box $i$ is $0$ or $r_i$, with probabilities $1-p_i$ and $p_i$. Here's another example. Suppose the prize is uniformly distributed over $[0,r_i]$ and $r_i/2<c_i<r_i$. Then the Gittins index is in the undiscounted case is the solution to

$g_i= -c_i +\int_0^{r_i}\max(g_i,u)(1/r_i)du= -c_i +(g_i^2/r_i+r_i/2)$.

The idea here is that Pandora is indifferent between taking home $g_i$, or opening box $i$, at cost $c_i$, and then taking home the best of either $g_i$ or the prize she finds in the box.

This gives $g_i= r_i-\sqrt{2c_ir_i-r_i^2}$, with $0<g_i<r_i$.

The Gittins index theorem is one of the most beautiful results in the field of Markov decision processes. Its discovery and proof in 1974 is due to John Gittins. The proof I have given in today's lecture is very different to Gittins's original proof. It the simplest way to prove the theorem and was first presented in On the Gittins index for multiarmed bandits. Ann. Appl. Prob. 2, 1024-33, 1992.

Lecture 6

Today we looked at some stopping problems. They crop up all over the place. They are present in financial mathematics in the theory of option pricing (Black-Scholes). The holder of an American option is allowed to exercise the right to buy (or sell) the underlying asset at a predetermined price at any time before or at the expiry date. The valuation of American options is essentially an optimal stopping problem.

You can read more about Bruss's odds algorithm in his paper: "Sum the odds to one and stop" Annals of Probability, Vol. 28, 1384–1391, (2000). I showed you  how to use this to address a Secretary Problem in which the candidates arrive in groups, of sizes $n_1,n_2,\dotsc,n_h$. I wonder what is the best order to interview the groups? Should we see large groups first, or small groups? I forgot to mention that the optimal success probability when using the odds algorithm is $q_{s^*}\cdots q_n(r_{s^*}+\cdots+r_n)$ and that this is always at least $1/e$, provided $r_1+\cdots+r_n\geq 1$.

Let me finish with some hints about questions on Examples Sheets 1 and 2. Question 6 on Sheet 1 can be solved by realizing that there are only two stationary Markov policies. You simple need to decide which is best. Question 7 is a simple stopping problem that can be solved using a OSLA rule. Question 8 is tricky. You should use Theorem 4.2. 

Question 9 on Sheet 1 is important because it should convince you that it is possible to solve stochastic dynamic programming equations using linear programming (at least if both state space and action space are finite.)  It there are $n$ states and $m$ actions (controls) available in each state then we will have an LP in $n$ variables, with $nm$ linear inequality constraints. 

When on sheet 2 you do Question 2 you might think about using Bruss's Odds Algorithm. Although you cannot apply the algorithm directly, you should be able to solve this problem using the same scheme of proof as we used to prove the optimality of the odds algorithm in this lecture.