An Improved Relaxation for Oracle-Efficient Adversarial Contextual Bandits

Summary

This paper investigates the contextual bandit problem where the contexts are sequentially sampled from a known i.i.d. source, and losses are generated adversarially. The primary focus is on developing oracle-efficient algorithms that minimize the expected regret (the expectation over both the context's randomness and the algorithm's internal randomness). Specifically, the paper demonstrates that for any finite policy set $\Pi$ with an value-ERM oracle (capable of finding the minimal policy loss given any sequence of losses), one can achieve an oracle-efficient regret bound of the order $T^{2/3}(K\log|\Pi|)^{1/3}$, where $K$ is the number of arms. This finding surpasses the previous bound of order $(TK)^{2/3}(\log |\Pi|)^{1/3}$ in Syrgkanis (2016). The proof technique essentially follows the relaxation-based argument from Rakhlin and Sridharan (2016) and Syrgkanis (2016). However, a distinguishing feature of this paper is the introduction of novel Rademacher vectors when defining the relaxation. The authors successfully incorporate these new Rademacher vectors into the analysis framework established by Syrgkanis (2016), thereby advancing the current state of the art.

Strengths

The main strength of this paper is the oracle-efficient regret bound that improves the state of the art. The authors also introduces several new ideas and techniques that is of independent interests.

Weaknesses

The submission does not seem to have any significant weaknesses. However, I have a few minor comments concerning the presentation: 1. The paper contains several typographical errors, including: - line 1: "for for" - line 284: isn't (ii) follows from the independence of $\epsilon_t$? - line 394: should be "Proof of Lemma 4" 2. It would be better if the authors could reference the corresponding appendix section in the main text where proof is provided. 3. For a more direct comparison with previous bounds, it would be beneficial to consider some specific values for $K$, such as setting $K=T^{\alpha}$, where $\alpha<1$. This would provide more tangible examples and help in understanding the practical implications of the bounds.

Questions

I have a couple of questions for the authors: 1. The paper currently focuses on the finite policy set. Could the techniques developed in this paper be utilized to enhance the Rademacher complexity-based bounds, as discussed in Rakhlin and Sridharan (2016)? 2. Could the i.i.d. assumption be relaxed? For instance, could it accommodate smooth adversaries as proposed in Haghtalab et al. (2022)?

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.

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.

Soundness

3 good

Presentation

2 fair

Contribution

3 good

Limitations

No issue with negative societal impact.

Summary

In this paper, the authors consider a classic contextual bandit problem with adversarial loss and stochastic context. Specifically, they proposed a relaxation-based algorithm which achieves $O(K^{1/3}T^{2/3}\log^{1/3}|Pi|)$ expected regret bound, improving upon the best known $O(K^{2/3}T^{2/3}\log^{1/3}|Pi|)$ obtained by Syrgkanis et al., 2016 under the same assumption. The algorithm is oracle-efficient, which requires $K+1$-number of call to the ERM oracle. The main improvement upon the algorithm proposed in [Syrgkanis et al., 2016] is a new relaxation expression. Specifically, they replace the random vector $\epsilon_t$ with all entries a Radamacher random variable by a random vector with a uniformly chosen entry being the Radamacher random variable. The reason for this improvement I think is due to the fact that the loss for each action has a uniform $\frac{\gamma}{K}$ probability to be observed and recorded in the loss estimator construction, which is missed in the construction of [Syrgkanis et al., 2016].

Strengths

- This paper considers a classic contextual bandit problem with a provable better theoretical guarantee in the expected regret bound. - The writing of this paper is clear. - The proposed algorithm is clear, which is mainly based on the relaxation-based algorithm proposed in [Syrgkanis et al., 2016] but with a better construction on the relaxation function $Rel$. - The proofs also look correct to me. Although the modification compared with [Syrgkanis et al., 2016] is not that much, the new construction on this relaxation function looks interesting to me.

Weaknesses

- One concern is the significance of the obtained results. Compared with [Syrgkanis et al., 2016], the improvement is a factor of $K^{1/3}$. Although the author argued that this improvement can be significant when considering continuous action space with a discretization, I think the order on $T$ may be more important. The main difficulty from obtaining the $\sqrt{T}$ regret bound seems to be the fact that the loss estimator is meaningful only when the algorithm explore, which also appears in the BISTRO+ algorithm proposed in [Syrgkanis et al., 2016]. - Minor part: I think the algorithm actually does not require the context distribution to be known but instead require sampling from the context distribution. So I think the abstract description is not accurate, meaning that the result is stronger. - Minor typo: (1) Line 160: minimizes -> minimize (2) Line 266-267: missing a right bracket

Questions

- I wonder whether it is possible to further generalize this relaxation-based algorithm to achieve $O(\sqrt{T})$ type result? - In addition, the current algorithm requires fresh samples of the stochastic context distribution, which is the same as what is assumed in [Syrgkanis et al., 2016]. I wonder whether it is possible to remove this assumption, since in some applications, this assumption may not hold.

Rating

6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.

Confidence

3: You are fairly confident in your assessment. It is possible that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.

Soundness

3 good

Presentation

4 excellent

Contribution

3 good

Limitations

See Weakness and Questions.

Summary

The paper studies the problem of minimizing regret for online adversarial contextual bandits using an ERM oracle. If one doesn't care about oracle efficiency, then the well known EXP4 algorithm achieves the optimal rate. However, the best previous oracle-efficient result is due to [Syrgkanis et al. '16]. This paper improves a factor of $K^{1/3}$ in the regret for this problem over prior work, where $K$ is the number of arms. The algorithm uses $O(K)$ calls to the oracle in every round. Their proof relies on a new relaxation under the relax-and-randomize framework of [Rakhlin-Sridharan] which has reduced variance compared to prior works.

Strengths

- The paper is exceptionally well written. The problem statement, relationship to prior works, explanation of the main contributions, and technical aspects of the proof are all very clear. As such, it was easy for me to follow and understand. - The relaxation function that is used to improve the dependence on $K$ seems to be novel.

Weaknesses

- The only weakness is that I'm not sure how significant the contribution/impact of the paper is: it only amounts to a $K^{1/3}$ improvement in the regret. There is still a substantial gap between the upper bound and lower bounds. The paper also doesn't really touch upon whether their rate is improvable for oracle efficient algorithms (we know EXP4 attains the optimal regret if we don't care about oracle efficiency), potentially hinting at some sort of separation result.

Questions

I have checked almost all of the proofs of the paper. I had a few questions, ranging from questions on the technical details to more higher-level questions. 1. What is the oracle complexity for prior works? Can some discussion on this be included (if it is interesting)? 2. What can be done if the learner does not have sample access to the distribution $\mathcal{D}$? Is learning possible here? EXP4 does not require this additional assumption. 3. Line 191: what is meant by the "discretization scheme"? 4. Any intuition for what the parameter $\gamma$ controls? Should we expect any improvements in the final bound with a changing $\gamma_t$? 5. While I understand the construction of the relaxation function (specifically the design of $\epsilon_t$ and $Z_t$), it is still quite mysterious. I see how it is used in Lemma 9. Perhaps the authors could include more intuition on this. 6. In theorem 6, what is the quantifier over the $x_t$? Are we also taking expectation wrt $x_t$? 7. writing comment: In Lemma 9, perhaps $\delta$ should be properly defined. It is defined in the previous lemma, but as is, Lemma 9 cannot be read "independently" Maybe state the definition of $\delta$ before the statements of Lemma 8 and 9? 8. writing comment: In appendix, you write Theorem 4, but in the main text, it is stated as Lemma 4. 9. In line 398, the derivation here could include more explanation. 10. line 403: "We reiterate that each $p_t(i) \le \gamma$" I thought by construction we had $p_t(i) \le \gamma/K$, so we can't put $\gamma$ mass on any arm $i\in [K]$ (as stated in line 211). Am I missing something here? 11. line 432: I did not understand why the probability of $\hat{c}_t$ taking the value $Ke_i/\gamma$ is at most $\gamma/K$. By Eq (6), don't we have the probability is at least $\gamma/K$? More speculative, for my own understanding: - Do you think that this relax/randomize strategy has limitations? It seems like we cannot substantially improve this bound to get $\sqrt{T}$-style regret. - Can the arguments from [Hazan-Koren '16] be used to get lower bounds against oracle-efficient algorithms? - Superficially, the guarantee that you get seems to be what one would expect if they adapted a "PAC" algorithm that got $K/\epsilon^2$ sample complexity using an online2batch conversion (of course, here in the adversarial setting "PAC" doesn't make sense because the costs are adversarial). Does this hint at a limitation of oracle-efficient algorithms?

Rating

6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.

Confidence

5: You are absolutely certain about your assessment. You are very familiar with the related work and checked the math/other details carefully.

Soundness

4 excellent

Presentation

4 excellent

Contribution

2 fair

Limitations

None.

Summary

This paper proposed a new algorithm for Oracle-Efficient Adversarial Contextual Bandits that achieves the best known regret bound and improve upon the previous best bound in its dependency on the action set size $K$.

Strengths

The algorithm is elegant. The paper is well-written and pleasant to read. The theoretical result is sound.

Weaknesses

The theoretical results are sound, but I believe for any work that make effort towards some type of computational efficiency, oracle-efficiency being one of them, experimental evaluation is always appreciated.

Questions

NA

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.

Confidence

3: You are fairly confident in your assessment. It is possible that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.

Soundness

4 excellent

Presentation

4 excellent

Contribution

4 excellent

Limitations

NA

Thanks

Thank you for your response to my questions. Through I still think the improvement over K is not that significant (from order 2/3 to order 1/3), I agree that the technique used in the analysis is interesting and I keep my original score.