Multi-armed bandit problem with precedence relations

Details Multi-armed bandit problem with precedence relations Multi-armed bandit problem with precedence relations

2007-02-27

arxiv.org/abs/math/0702819v1

IMS Lecture Notes Monograph Series 2006, Vol. 52, 223-235

Mathematics

Statistics Theory

Published at http://dx.doi.org/10.1214/074921706000001067 in the IMS Lecture Notes Monograph Series (http://www.imstat.org/p

Scientific paper

10.1214/074921706000001067

Consider a multi-phase project management problem where the decision maker needs to deal with two issues: (a) how to allocate resources to projects within each phase, and (b) when to enter the next phase, so that the total expected reward is as large as possible. We formulate the problem as a multi-armed bandit problem with precedence relations. In Chan, Fuh and Hu (2005), a class of asymptotically optimal arm-pulling strategies is constructed to minimize the shortfall from perfect information payoff. Here we further explore optimality properties of the proposed strategies. First, we show that the efficiency benchmark, which is given by the regret lower bound, reduces to those in Lai and Robbins (1985), Hu and Wei (1989), and Fuh and Hu (2000). This implies that the proposed strategy is also optimal under the settings of aforementioned papers. Secondly, we establish the super-efficiency of proposed strategies when the bad set is empty. Thirdly, we show that they are still optimal with constant switching cost between arms. In addition, we prove that the Wald's equation holds for Markov chains under Harris recurrent condition, which is an important tool in studying the efficiency of the proposed strategies.

Affiliated with

Also associated with

No associations

Rating

Multi-armed bandit problem with precedence relations does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Multi-armed bandit problem with precedence relations, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Multi-armed bandit problem with precedence relations will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-207208