Essays on sequential analysis: Multi-armed bandit with availability constraints and sequential change detection and identification

This dissertation addresses two sequential decision problems: the multi-armed bandit and the sequential change detection and identification problems. As exemplified by the Gittins index policy (Gittins 1979) and Wald's SPRT (Wald 1947), these problems can be greatly simplified and optimal solutions can be computed relatively easily. However, these theories depend on the special structures of the underlying problems and do not hold when relaxed. We generalize these problems in order to capture important real-world features and pursue computationally tractable and near- or asymptotically-optimal solutions.;We first study two generalizations of the classical bandit problem in which arms may become unavailable temporarily or permanently, and in which arms may break down and the decision maker has the option to fix them. It is shown that an optimal index policy does not exist for either problem. Nevertheless, there exists a near-optimal index policy in the class of Whittle index policies that cannot be dominated uniformly by any other index policy over all instances of either problem. Whittle indices are evaluated numerically for Bernoulli arms with unknown success probabilities.;We then study the joint problem of change point detection and sequential hypothesis testing. Based on a sequence of observations, one needs to detect a sudden and unobservable change at the earliest and identify its cause accurately. We first consider the general case and then specialize the result in the i.i.d. case. We propose simple sequential decision strategies and show their asymptotic optimalities under two Bayesian formulations. We verify the results numerically using an example where the observation process is Gaussian.