
\documentstyle[12pt]{article}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%TCIDATA{OutputFilter=Latex.dll}
%TCIDATA{LastRevised=Tue Feb 10 14:20:52 2004}
%TCIDATA{<META NAME="GraphicsSave" CONTENT="32">}
%TCIDATA{Language=American English}
%TCIDATA{CSTFile=article.cst}

\oddsidemargin -10 mm \topmargin -11 mm \textheight 225 mm
\textwidth 178 mm


\begin{document}


%\pagestyle{empty}
%\newpage
\title{
A (Gittins) Index Theorem for Randomly Evolving Graphs.
}

\author{
Isaac Sonin (joint with E. Presman) \\
Dept. of Mathematics, UNC Charlotte, Charlotte NC 28223.
}

\date{March 1, Computational Finance Seminar in CMU}

\maketitle

We consider the problem which informally can be formulated as follows.
Initially a finite set of independent trials is available. If a Decision
Maker (DM) chooses to test a specific trial she receives a reward depending
on the trial tested. As a result of testing, different outcomes can occur.
With some probability, which depends on the trial, the process of testing is
{\it terminated} and with complementary probability the tested trial becomes
unavailable but some random finite set (possibly empty) of new independent
trials is added to the set of available trials. This process can be
repeated, but the total number of potential trials is finite. A DM knows the
rewards and transition probabilities of all trials. At each step she can
either {\it quit} or continue. Her goal is to select an order to test trials
and a quitting time to maximize the expected total reward.

On one side this problem is a generalization of a ''least cost testing
sequencing'' problem solved independently by a few authors in 1960 (see
[1]), and on the other side is a generalization of the so called Multi-armed
Bandit problem with independent arms (see, for example, [2]). It is also a
generalization of [3] where the set of new trials was deterministic. This
model allows more general economic interpretation when trials are
interpreted as economic projects which bring some rewards but with some
probability may also result in the termination of decision process. \

Formally the model can be formulated as a Markov Decision Process model
defined on a graph which is a directed forest $F_{0}$ with a finite number
of edges, where each edge represents a possible trial. A state $x$ is either
an absorbing state $x_{\ast }$, or consists of a subset (possibly empty) of
edges of $F_{0},$ available for testing at that moment. For each edge $e$ of
the forest, denote by $T(e)$ the directed tree which consists of all edges
which follow $e.$ Given an initial state $x$ and strategy $\pi ,$ the goal
is to maximize the expected total reward, $R_{x}^{\pi }.$ The classical
Gittins model will be a special case of this model if we allow forest $F_{0}$
to be infinite and set all termination probabilities equal to $(1-\beta )$
where $\beta $ is a discount coefficient.\

{\bf Main Problem:} {\it Given an initial state} $x$, {\it maximize} $%
R_{x}^{\pi }$ {\it over all strategies}.\

Let $\gamma (e)$ be a function on a forest $F_{0}$. A strategy $\pi $ is
called a $(\gamma ,c)$-priority rule or simply a priority rule if $\pi $
tests each time the edge with the highest value of $\gamma $ among all
available edges with values greater than $c$, and quits otherwise. Let $%
S_{e}^{\pi }$ be the probability of termination under priority rule $\pi $\
with an initial state $x=e.$\

{\bf Auxiliary problem:} {\it For any edge} $e$,{\it \ maximize} $R_{e}^{\pi
}/S_{e}^{\pi }$ {\it over all priority rules defined on} $T(e)$.

Let $\alpha (e)$ denote the result of maximization in the Auxiliary problem.
Our main result is similar to the celebrated Gittins result and the result
in [3] but index $\alpha $ has a more general structure.\

{\bf Theorem}. a) {\it A (unique) optimal strategy in the Main Problem is a}
$(\alpha ,0)$-{\it priority rule},

(b) {\it a (unique) optimal strategy in the Auxiliary Problem is a} $(\alpha
,\alpha (e))$-{\it priority rule defined on} $T(e)$.\ \

{\it References.}

\noindent \lbrack 1] Mitten, L. G. (1960) {\sl An Analytic Solution to the
Least Cost Testing Sequence Problem. J. of Industr. Eng. 11, no. 1, 17.}

\noindent \lbrack 2] Berry, D. A.; Fristedt B. (1985) {\sl Bandit Problems.
Sequential Allocation of Experiments. Monographs on Statistics and Applied
Probability, Chapman \& Hall, London.}

\noindent \lbrack 3] {\sl Denardo E. V., Rothblum U.G., Van der Heyden L.
(2003), Index Policies for Stochastic Search in a Forest with Application to
R\ \&\ D Project Management, manuscript.}\

\end{document}
