Improved Regret Bounds for Oracle-Based Adversarial Contextual Bandits
We propose a new oracle-based algorithm, BISTRO+, for the adversarial contextual bandit problem, where either contexts are drawn i.i.d. or the sequence of contexts is known a priori, but where the losses are picked adversarially. Our algorithm is computationally efficient, assuming access to an offline optimization oracle, and enjoys a regret of order O((KT )
The authors studies the contextual MAB problem. The features across the periods are generated i.i.d. from a distribution known to the decision maker, but the losses across the periods are adversarially generated. By designing a new "partial information relaxation" and using a recent framework for contextual MAB proposed by Rakhlin and Sridharan, the authors manage to improve the regret from the state of the art, namely O(T^(3/4)), to O(T^(2/3)).   The key to improvement is the incorporation of a Rademacher term (the middle term) in the partial information relaxation defined between Line 129 and 130. This term has two Rademacher random variable, Z_t and epsilon_t. My understanding is that the rv Z_t ensures that the partial information relaxation is valid (satisfying eqns (2, 3)), while the rv epsilon_t ensures that the relaxation term grows in a rate of sqrt(T) (conf Lemma 2) instead of T, which brings about the improvement.
The paper makes some interesting contribution by proposal a new partial information relaxation to improve the regret bound. The analysis of the partial info relaxation bears some similarity to that in Rahklin and Sridharan, but the inclusion of the Radamacher term is new. By using Lemma 2, the bound is improved. While this is definitely a new result and there are new ideas, the similarity to current literature kind of compels me to give a '3' instead of a '4' for the Novelty/Originality and Technical Constribution scores.  Presentation: The paper is concise and well written, but I think that the proof of admissability between 5 and 7 is too "straight-lined". The unraveling  and bounding from Line 156 to Line 188 is rather long, but it would be more readable if the authors first highlight the major steps in the calculation, and then explain how to go from one major step to the next. This will give a better feel on your design of partial information relaxation. In particular, I think you should label "the quantity inside the expectation" between Line 162 and 163 to avoid ambiguity. A clear presentation of the proof is very important, since it will guide future readers on the design of partial information relaxation in the framework.