Session 6

In today's session we looked at some more advanced topics, which previous sessions have prepared us to understand. I focused on some problems that I have studied in my own research.

With hindsight, I may have been too ambitious in imagining what I might cover this morning. I hope that my notes will help fill in gaps if you wish to learn more.

In the end, we covered the notion of Whittle indices for restless bandits. We saw that the policy they define is optimal, or near optimal, in the limit that the number of identical bandits $n$ tends to infinity. This was by the fact that in large-$n$ systems the proportions of bandits in the states have a "fluid model", which is linear within polyhedral regions.

In the second part we looked at stochastic sequential allocation and assignment problems. The assignment problem (SSAP) has a surprising answer: that the optimal strategy can be described in terms of thresholds that do not depend on the values of the $p_i$. The proof is cute and is worth understanding.

I mentioned Rhoda Righter's nice treatment of a SSAP with arrivals, in which the incentives for individual (selfish) behaviour by workers can be made to coincide with the socially optimal behaviour. This is also true in the SSAP without arrivals, if the jobs arr offered to the workers in decreasing order of their $p_i$. For example, with $n$ workers present, the $i$th will accept the job iff it has been declined by workers $1,2,\dotsc,i-1$  and then is value $X$ is at least $a_{i,n}$, which is the expected value of the job that will be assigned to $i$th worker if she rejects this currently offered  job. It will be declined by the previous workers precisely if $X <  a_{i-1,n}$.

There was not time to discuss all problems. I did not fully discuss all the solutions to Problem Sheet 2 5-7. The model solutions are now on the web site.

Some reference about the Bomber Problem and its relatives are in the previous post. The slides I used to talk to are here. 

ABCs of the Bomber Problem

I briefly spoke today about the infamous Bomber Problem. If you would like to read more, see ABCs of the Bomber Problem and its Relatives, Weber, 2011. There is also a talk about this here. This problem has been open for over 35 years, and has been said by researchers who know it to be highly additive. It is very infuriating that for a problem with such a very simple dynamic programming equation an "obvious" fact cannot be proved or disproved.

$F(n,t)$ is the probability that a bomber plane, which is potentially attacked by enemy fighters $t$ times, can successfully defend itself against all such attacks, when starting with a supply of $n$ air-to-air missiles. The probability of surviving an attack by using $k$ missiles is $(1-\theta^k)$, where $0 < \theta < 1$.

$F(n,t) = q F(n,t-1) + p \max_{k\in\{1,\ldots,n\}}(1-\theta^k)F(n-k,t-1)$

$F(n,0)=1$

Conjecture B is that the maximizing $k$ is nondecreasing in $n$.

Many problems very similar to this are easy to solve, such as the stochastic sequential investment problem (of Derman Leiberman and Ross, described on page 34 of notes). Typically the proofs methods are similar to that in Problem 7 of Problems Sheet 2.

Klinger and Brown's 1968 paper is here.

Session 5

You will find that the policy improvement algorithm is useful in answering Problems 1 and 2 on Problems Sheet 3. In Problem 1, 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 Problem 2 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.

I have a personal fondness for some things I talked about the second half today. Theorem 10.1 (and extensions of it to other distributions beyond exponential) was one of the things that I proved in my Ph.D. dissertation in 1980. The Lady's Nylon Stocking Problem was a fairly famous unsolved problem. It gave me something to talk about with non-mathematically inclined fellows when I first became a research fellow. The paper is  Scheduling jobs with stochastic processing requirements on parallel machines to minimize makespan or flow time. J. Appl. Prob. 19, 167-182, 1982.

The method of uniformization that I described in this lecture seems to have been introduced by Jensen (1953), but it was first used extensively in solving queueing problems in the late 1970s (by Grassman (1977) and Keilson (1979)). Here is a quote from a recent 2011 paper by Rhonda Righter, Stochastic sequential assignment problem with arrivals, Probability in the Engineering and Informational Sciences, 25, 2011, 477–485:

Proof. We consider the equivalent discrete-time problem by uniformizing with uniformization rate $\lambda + \gamma + \alpha = 1$, and we use value iteration (i.e., induction on a finite time horizon, $n$).

The Wikipedia article has more about it and summarises the method in these words:

The method involves the constructions of an analogous discrete time Markov chain, where transitions occur according to an exponential distribution with the same parameter in every state.

I have used this idea many dozens of times in my own research. It is usually the best first step to make when  tackling a continuous-time Markov decision problem.