UCL algorithm corrections

[Could not find the bibliography file(s)

There was a subtle but small error in the proofs published in [?]. We have corrected the error in a new appendix G added to the arXiv version of the paper, available at https://arxiv.org/abs/1307.6134v4. These corrections also apply to other papers which built off of the results in [?], including [?], and [?].

The error arose from our application of concentration inequalities, sometimes known as tail bounds. In the originally-published proofs, we condition on the number of times that the algorithm has selected arm up to time . Since the arm selection policy depends on the rewards accrued, and the rewards are dependent random variables. In the correction, we build upon an alternative concentration inequality that accounts for this dependence and show that proofs of all the performance bounds follow a similar pattern with slight modification to the decision heuristic.