Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: summary: This paper focuses on parametrized contextual bandit problems, and their analysis via the Russo-Van Roy information ratio framework. The main contribution is to observe that one can analyze information gain on the "lifted" level of the "underlying context" instead of the "optimal action". This leads to nice new regret bounds for logistic bandits. The analyses are clean and remove dependence on problem-dependent constants which were common in previous work. At a high level, it seems that the "lifted" information ratio may often be the right way to study parametrized contextual bandits. 
strengths_and_weaknesses: I like the results and the writing is very nice. 

As far as I can tell, the main problem is that the key idea is less novel than the authors seem to believe. In particular while the application to logistic bandits is probably new, at an abstract level the lifted information ratio seems to essentially be a special case of the notion of "learning target" discussed in https://arxiv.org/abs/2103.04047 and https://arxiv.org/abs/2201.01902. (The adversarial contexts may change things slightly, but it seems mostly inconsequential for my comment.) I expand on what to do about this in the "Questions" section. In short, I think the submission should probably be revised to take this literature into account, and then resubmitted to a future conference (where I would support its acceptance).


questions: The most pressing suggestion is to incorporate the prior work on general learning targets. Assuming I'm not mistaken about the strong similarity, I suggest the authors make substantial revisions to acknowledge, compare with, and perhaps build upon this earlier work. For example, introducing the term "lifted information ratio" seems inappropriate if the idea already has a name. I think the submitted paper still has plenty of merit, and it seems plausible to me that the application to logistic bandits gives a more convincing application of this idea than the previous works I mentioned. I'm not familiar enough with the literature to say. If I'm confused about this point, please let me know and I will be happy to raise my score.

I have a few other questions and comments:

1. The authors write: 

"When considering i.i.d. contexts and finite policy classes, one can apply the theory of Russo and Van Roy [2016] and treat policies as actions to obtain regret bounds scaling with the entropy of the optimal policy, but this can lead to a polynomial dependence on the number of contexts." 

I would appreciate some elaboration on this point. My understanding is that the authors have in mind the setting of Thompson sampling with changing feedback graphs G_t (which for contextual bandit would be a union of K vertex-disjoint cliques). I believe the regret bounds here are of order \sqrt{TK H} where H is the entropy of the optimal policy (e.g. https://arxiv.org/abs/1805.08930 or section 8 of https://arxiv.org/abs/1902.00681). I don't see this polynomial dependence on the number of contexts anywhere and would like some clarification. It's quite possible that I am misunderstanding something basic and I apologize if this is the case.

2. In line 101, I was a bit surprised that the adversary does not know \theta^*. It would be nice to have some commentary on whether this is likely to be truly essential, when it is used, if it is required in related work, etc. On its face it seems to detract a little bit from the picture.

3. At the end of page 7, I was confused about the Bayesian telescoping argument. In particular it looks to me like the usual entropy chain rule should suffice: the expected information-gain at time t is by definition the average decrease in the entropy of \theta^*. Summing and using the fact that entropy is always non-negative, the upper bound of H(\theta^*) should follow. So it seems like the calculation was overcomplicated a bit and I cannot tell why.

4. Equation (1): missing a comma in the first \ell(\cdot) expression.

5. A positive comment to finish: I appreciated that the authors focused on countable priors while making it clear that this is just for convenience. I thought this choice made things quite pleasant to read.


limitations: N/A
review_title: null

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: summary: The authors study the Bayesian regret of Thompson sampling with binary losses and adversarial contexts. Adapting the information theoretic approach from Russo and Van Roy, through a definition of lifted information ratio, they provide a regret bound similar to the non-contextual case. This leads to state-of-the-art regret guarantees in many well-known cases covered by the proposed setting. Notably, they prove a regret bound for K actions, and Lipschitz logits which is independent on the slope of the link function. 
strengths_and_weaknesses: Strengths
- The lifting of information ratio is supported by the intuition that the information of the optimal action in one context may be useless in the other context. Thus substituting the mutual information between optimal action, and taken action and loss, with the mutual information between true parameter, and the loss resolves the problem.
- The adaptation of the information theoretic framework for Bayesian regret bounds in adversarial contextual setting is new. This has the potential for generalization in many other settings where information theoretic framework is used.
- The current approach results in state-of-art regret guarantees in many problems with adversarial contexts.
- The relation to the “decoupling coefficient” proposed by Zhang is also interesting (but this raises some question as well).


Weaknesses
- Moving away from the mutual information between optimal action to true parameter suggests we may end up with worse scaling w.r.t. the number of actions. However, that does not seem to be the case as seen in Lemma 3 which provides a $log(K)$ regret bound for $K$ actions. Maybe the authors should expand on how that is achieved. 

- Although the intuition supports the lifted Information ratio approach, it will be good to more rigorously point out why the previous information ratio fails in the contextual case. 

- Zhang explicitly mentions that TS may not be efficient in some cases, and introduces a bias towards higher reward in the Feel Good TS  approach. In light of that, the current connection seems to suggest TS suffice, at least for Gaussian case. Is this special for Gaussian case, and will fail in more general situations?


- Can there be an approach where we can judicially choose between the mutual information between optimal action, vs the true parameter while analyzing TS? It will be great if such an approach is found, as we can incorporate that in the analysis. Some comments will be interesting.

Post rebuttal:
- The current paper seems like a special case of the the notion of "learning target" discussed in https://arxiv.org/abs/2103.04047 and https://arxiv.org/abs/2201.01902 (as pointed out by another Reviewer).


questions: - Please look at the weakness part. Addressing the first two points will improve the paper.

limitations: Being a theoretical work any adverse social impact is hard to foresee.
review_title: null

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: summary: Previously, information ratio was used to bound regret of Thomspon sampling algorithm for multi-armed bandits. This paper provides examples that information ratio loses its usefulness in deriving bounds for contextual bandits. They introduce a new lifted information ratio which deals with information gained about parameter instead of best action. Using this ratio, the authors derive regret bounds for Thomspon Sampling. Using the bounds, they derive regret bounds under several interesting cases.
strengths_and_weaknesses: Strengths:
Lifted information ratio is an intuitive yet interesting quantity which authors motivate quite well. They also provide tight regret bounds using the new quantity.

Weaknesses:
As paper mentions, they don't provide any tractable algorithms and leave that task for future. It would be better if they can add more discussion on this.
questions: Paper can benefit more form discussion on tractability.
limitations: Satisfied with authors responses.
review_title: null

Meta-review: metareview: The paper presents an analysis of the Bayesian regret of Thompson Sampling algorithm in contextual bandits under an adversarial context process. The authors express the regret as a function of the so-called lifted information ratio. This information theoretical quantity is a natural extension of those introduced by Russo and Van Roy. The analysis provides new regret upper bounds for logistic bandit, and comes with simpler and elegant proofs. 

The reviewers easily reached a consensus on this paper. It is very well written, easy to follow, and provide very interesting contributions.

The discussion phase gave the opportunity for the authors to correct the related work section, and in particular to re-position the paper compared to papers pointed out by during the review process.  

confidence: Certain
Decision: Accept