Threshold Bandit, With and Without Censored Feedback
We consider the Threshold Bandit setting, a variant of the classical multi-armed bandit problem in which the reward on each round depends on a piece of side information known as a threshold value. The learner selects one of K actions (arms), this action generates a random sample from a fixed distribution, and the action then receives a unit payoff in the event that this sample exceeds the threshold value. We consider two versions of this problem, the uncensored and censored case, that determine whether the sample is always observed or only when the threshold is not met. Using new tools to understand the popular UCB algorithm, we show that the uncensored case is essentially no more difficult than the classical multi-armed bandit setting. Finally we show that the censored case exhibits more challenges, but we give guarantees in the event that the sequence of threshold values is generated optimistically.
The authors begin by providing an alternative proof for the regret bound of UCB. The endeavor of this seems to be to introduce the "potential trick" which the authors later use in the threshold setting. To my understanding, the threshold setting considered in this paper is a generalization of the UCB setting provided that the reward functions are all Bernoulli 0-1. To see this, one can fix c^t=c for all t. Then clearly the dominating arm is the one that maximizes $P(X^t_i \ge c)$. The distribution of the reward function $D_i$ is $1 w.p. P(X^t_i \ge c)$ and 0 w.p. 1- $P(X^t_i \ge c)$. I was wondering if a more appropriate generalization would be to reward $X^t_j$ provided it crosses the threshold. Probably in the setting of Dark pool brokerage this setting may find an application.  Coming back to the threshold UCB described in the paper, supposing $c^t=c$ for all $t$ then we are back in the UCB setting. When the sequence of thresholds is predetermined, one does not expect the analysis to deviate too much from Auer et. al. Having said that, as the authors state, the potential trick certainly fits in well.  The non-trivial threshold setting (uncensored and censored) is when $c^t$ is non-deterministic. Provided that $c^t$ takes values from a finite set the authors provide a regret bound that uses the DKW inequality to determine $f$, which in turn is used to fix the two auxiliary functions that allows for the potential trick to be applied. As the authors explain, one cannot just count the number of bad-arm-pulls especially when $c^t$ is not constant.  For the setting of the censored feedback setting, the authors provide a new estimator based on the Kaplan-Meier estimator, then go on to find $f$ (error bound for the estimator). The regret bounds should now proceed as in the previous sections.   Finally, they illustrate that the ordering of the threshold values affect the cost of learning. This is to be expected. The cost also seems to depend on how many values the threshold can take. 
It would be interesting if the authors can justify why are the new rewards are 0-1 and not $X^t_j$ or in general some different distribution provided the threshold conditions are met.  It seems that the likeness of UCB and DKWUCB is due to the uniform convergence of the empirical distributions to their "means". Does this mean that we can let $c^t$ take values over a continuous range provided such uniform-convergence-property hold.   There should be a way to get around assuming that argmax_i F_i(j) is unique. This would certainly make it more applicable. Or is it that the $c^t$ may be perturbed to justify the assumption.  It would be interesting if the authors can provide a detailed setting in a practical application wherein the $c^t$'s are non-deterministic/uniformly distributed over a finite set.  The potential trick seems to capture the scenario in sequential decision settings wherein the "good arm"/right action changes with time. Can there be more insight into where the potential trick will prove helpful?