Summary
The submission considers semi-adversarial contextual bandit setting --- where d-dimensional contexts x_t are drawn iid, where some opponent picks K loss functions that are linear in the contexts at the beginning of each round, before the actual context x_t is drawn, and where he learner picks one of the K loss functions and suffers the corresponding linear loss. This setting was introduced by Neu and Olkhovskaya (COLT 2020), who provided 'zero-order' regret bounds of order \sqrt{K d T}. The present submission refines the regret bounds into first-order (for non-ngative losses, as usual) and second-order regret bounds, involving respectively the cumulative loss of the best static policy and the expected sum of instantaneous variances of the rewards obtained by the algorithms (and generalizations thereof). This is achieved by considering a continuous version of exponential weights, à la Cover (1991), and by leveraging techniques introduced by Ito, Hirahara, Soma, and Yoshida (Neurips 2020) for such refined first-order and second-order bounds in the setting of non-contextual adversarial linear bandits.
The key to the results is the reduction (18) of this semi-adversarial contextual bandit problem into a linear bandit problem, as underlined in lines 285-288.
Strengths
The submission has a clear technical focus, and combines in a neat way techniques from Neu and Olkhovskaya (COLT 2020) and Ito, Hirahara, Soma, and Yoshida (Neurips 2020). The proof sketch provided on pages 6--8 is well structured. Up to some typos and some unclear pieces of notation, I can only praise the writing.
Weaknesses
My main issue is with the algorithm, which relies on distributions that are difficult to compute exactly---as always with continuous exponential weights (see articles from Vempala and co-authors at the end of the 90s, commenting on Cover's original contributions). Allowing \epsilon--approximations reduces the computational burden (see Section 3.3) but the effect of using these \epsilon--approximations on the regret bounds is not discussed. Would this add some \epsilon T terms? Then, it would probably be wise to pick \epsilon = 1/T, not to kill with this extra term the possible fast rates of convergence yielded by first- and second-order bounds. (Also, it is not clear to me from Section 3.3 whether these \epsilon--errors propagate and get worse and worse as t increases, or if for each t, we may and should compute an \epsilon--approximation from scratch, not based on previous probability distributions.)
Another issue would be that I am unsure of what the second-order bound of Theorem 3.2 brings: it is highly general, and no corollary or example for the functions m_t are provided (except, I guess, the choices m_t \equiv 0). More generally, I am unsure of how important it is to get refined bounds with a rather non-practical algorithm based on continuous exponential weights.
A more minor issue is about the assumption of log-concavity. It is satisfied by many distributions (see https://en.wikipedia.org/wiki/Logarithmically_concave_function#Log-concave_distributions, and the submission could give examples) but is also not satisfied by other important ones.
Typos / Remarks
- Lines 96-97: rather cite Cover (1991) or to the very least the monograpu by Cesa-Bianchi and Lugosi (2006), instead of a 2018 reference
- Line 123: I believe you refer to it as \pi(X_t) and never use \pi(a|X_t)
- Line 131: Yes, this seems clear indeed
- Line 134: I would rather have written E_{t-1} instead of E_t
- Line 144 / Eq. (4); see also later occurrences like in Th.3.2: Is L^*_T the same as L_T^{\pi^*}?
- Algorithm 1: Say that each m_s is a function that is measurable w.r.t. \mathcal{F}_{s-1}
- Eq.(6): Somewhere earlier than in lines 291 and following, discuss the number of steps needed to achieve (6), i.e., geometric distribution with a parameter that you anyway bound in the proof---but mention it early, at latest on page 5 or in Section 3.3
- Line 185: Define somewhare what log-concavity of a distribution is, and provide examples
- Eq. (18) and comments in lines 285-288: This is the key step and it's somewhat hidden, I'd suggest to put it more in front
- Lemma 4.2: Notation is heavy and the result is extremely difficult to read, is there any way to make it smoother? That part and Eq. (19) should also be put more in front.
- Line 291: Missing word before 1 ('Algorithm' I guess)
- Appendices: Cauchy-Schwarz without a 't'
Questions
Please comment on the main two weaknesses that I listed.
Rating
5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.
Confidence
4: You are confident in your assessment, but not absolutely certain. It is unlikely, but not impossible, that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work.
Limitations
The authors are clear about the limitations, and in particular, on dependency of their regret bounds on K, which does not match, in the worst-case, the known \sqrt{d K T} regret bound. The discussion on page 9 is complete and upfront about the scope of their contribution.