printable pdf
比利时vs摩洛哥足彩 ,
university of california san diego

****************************

math 288 - probability

ernst presman

central economics and mathematics institute, russian academy of sciences

a simple proof of an (gittens) index theorem for graphs

abstract:

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 particular trial she receives a reward depending on the trial tested. as a result of testing a random finite set (possibly empty) of new independent trials is added to the set of available trials, and so on, but the total number of potential trials is finite. a dm knows the rewards and transition probabilities of all trials. on each step she can either stop testing or continue. her goal is to select a testing order and a stopping time to maximize the expected total reward. this problem has a long history and is related to the multi-armed bandit problem with independent arms. we prove that an index can be assigned to each possible trial, and the optimal strategy is to use on each step a trial with maximal index among those available. we give a simple procedure for constructing this index. this is joint work with isaac sonin.

host: ruth williams

june 6, 2003

11:00 am

ap&m 6438

****************************