Optimal cross-learning for contextual bandits with unknown context distributions

Summary

The paper studies the cross-learning problem in contextual bandits, and proposes a $\sqrt{KT}$ regret algorithm.

Strengths

The paper proposes an algorithm achieving $\sqrt{KT}$ regret using an epoch-based schedule. The algorithm achieves optimal regret without requiring knowledge of the context distribution.

Weaknesses

In applications (section 1.1 and section 4), it might be better to point out the explicit connection between cross-learning and bidding in 1st price auction / sleeping bandits. E.g. what is the context here in 1st price auction? The technical part was very hard to follow. I have doubts about the soundness of the technical approach, see questions below. The writing contains noticeable grammatical errors, e.g. line 214, line 237...

Questions

For the main algorithm: 1. Why divide epochs into length $\sqrt{T}$? 2. What exactly is the use of the 'rejection sampling' procedure, and how can this help with estimation? 3. line 212, what is 'same distribution' referring to? In line 200, what does changing distribution refer to? In line 238, is $\tilde{l}_{ckt} \in R^{K}$ or $R$? Similar question for $ \tilde{p}_{ckt} $.

Rating

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

Confidence

2: You are willing to defend your assessment, but it is quite likely that you did not understand the central parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.

Soundness

2 fair

Presentation

2 fair

Contribution

3 good

Limitations

The authors did not address limitations.

Summary

This paper studies contextual bandits in the ``cross-learning' setting. They propose an algorithm that attains nearly tight regret of $\tilde{\mathcal{O}}(\sqrt{TK})$. They achieves this by carefully separating the horizon into blocks of fixed size and coordinate the estimation of unknown distribution and the action played by the algorithm to remove the correlations. They apply their methods in first-price auctions and sleeping bandits and obtain nearly tight bounds.

Strengths

This paper is in general well-written. The considered setting is hard yet the theoretical bounds are nearly tight. The algorithm is carefully designed to decouple the distribution of the estimated unknown context and actions chosen and is nicely presented.

Weaknesses

The cross-learning setting is not so meaningful to me. At least, I think the authors are not doing a good job in motivating this setting. The only example provided is bidding in an auction, where different counterfactual values of the items. However, the context here is only one-dimensional, and the loss monotonously depends on the values, as a result, the cross-learning setting is more likely a byproduct of the specific one-dimensional structure rather than something common in practical applications.

Questions

1. What do the authors expect their algorithms, and regret bounds become if the cross-learning condition is dropped? Is there any reason essential to keep the conditions, other than making the regret bounds tighter? 2. In practice, how do you choose $L$? This length seems to be fixed for all time, and the algorithm is designed to deal with various unknown distributions. I wonder (1) how to tune $L$ apriori and (2) why a fixed $L$ could work for a large family of unknown distributions? Minor thing: In the proof of Lemma 6 on page 13, there seems to be an error in upper bounding $\beta_{e k}-1$, namely $4/\frac{7}{8} > 3$.

Rating

5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.

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

3 good

Contribution

3 good

Limitations

I don't see any limitations or potential negative societal impact of this work.

Summary

This manuscript studies the following missing piece in [Balserio et al. 2019]: in contextual bandits with cross learning (i.e. with a complete feedback graph across contexts), suppose that the contexts are stochastic with an unknown distribution, is there an algorithm that achieves a \tilde{\Theta}(\sqrt{KT}) regret? Note that when the context distribution is known, an EXP3-type algorithm in [Balserio et al. 2019] achieves the above bound. The key difficulty in this manuscript is to estimate the sampling probability when carrying out the EXP3 algorithm. There are two main ingredients in this manuscript: 1. Bypassing the high-probability UCB. Specifically, when \hat{f} is an estimate of f with |\hat{f} - f| \le a with high probability, the naive argument tells that 1 / (\hat{f} + a) \le 1/f with high probability. By leveraging the curvature of 1/x, the authors improved this result by showing that if in addition |E[\hat{f}] - f|\le b, then E[1/(\hat{f} + b)] \le 1/f provided that a \le \sqrt{f*b}. The final inequality is further ensured by the Bernstein concentration. This observation shows that one can use a smaller confidence bound (b instead of a), and essentially implies that the estimation of sampling probability is a much simpler problem and requires only sqrt(T) samples. This is the key to the success of the proposed algorithm. Significance: high. 2. Dealing with the dependence issue. To this end, the authors applied several tricks. First, decouple the rounds for loss estimation and sampling probability estimation. Second, use the target sampling distribution given two epochs before. Third, use the sampling probability estimates one epoch before. This involves additional technical analysis for the continuity of EXP3-type probability updates. Significance: medium. This result is applied to two problems. The first is the bidding in first-price auctions in [Balserio et al. 2019] with binary feedback, where this manuscript complements the result of [Balserio et al. 2019] by establishing a T^{2/3} regret when the private value distribution is unknown. Significance: medium. The second application is sleeping bandits with stochastic availabilities, where a sqrt{KT} regret is shown. This result greatly improves the existing ones in the literature in the sense that both the regret and the computation time are polynomial in (K, T). Significance: high.

Strengths

As summarized above, I really like two components of this manuscript: 1. An improved bound of |E[1/(\hat{f}+b)] - 1/f| taking into account both the L_infty and L_1 norm of |\hat{f} - f|. 2. Formulating the sleeping bandits as a cross-learning problem and its application.

Weaknesses

I do not see a major weakness for this manuscript. At the beginning I felt that this manuscript is a bit narrow in scope (i.e. finish a small missing piece in [Balserio et al. 2019]), but the application to sleeping bandits is very interesting. However, I still have to say that the writing quality is poor and the presentation of high-level ideas is obscure. I strongly urge the authors to improve the writing, including: 1. The explanation of the first technique on Page 4. Could you formulate it in a similar way to my point 1 in the summary? Also this result could be stated as a standalone lemma. In the paragraph, C_N is undefined too, and I don't know what N is. 2. There are lots of notations in the algorithm description, including p, q, s, f. The most confusing quantity to me is s, for which I spent quite a bit of time understanding its role. For an algorithm with several components, my general suggestion is to explain them piece by piece.

Questions

N/A

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

N/A

Summary

This paper studies the sequential learning problem with the presence if context, where the context is drawn iid from some unknown distribution and the losses are chosen by the adversary. The feedback, that learner observes, is the loss for any context for the chosen action. This paper improves the previous result in this setting, by showing the $\tilde{O}(\sqrt{KT})$ regret upper bound for the algorithm with running time that scales with the number of context at each time step. Authors demonstrate a range of real-world applications where such feedback model is useful.

Strengths

Authors improve the previously known result for the unknown distribution setting, by proposing the new technique on the estimation of the loss for this problem that allows remove the dependence between the data from which the losses and the context distribution are estimated.

Weaknesses

Some steps of the proof are omitted, so I could not verify the correctness of the proof. See Questions. For proposed applications, issues of the computation efficiency were not discussed.

Questions

Line 495, could you please give more details on the application of Lemma 3? It is not straightforward that this Lemma gives the inequality that is used in that sequence of inequalities. Loss estimation is only defined for steps $t_l$, so the fact that the algorithm ignores the half of the observations should affect this lemma. These quantities are not defined: - Equation after line 193, $p_{eL,c,k}$ - line 201, $s_{eck}$ Algorithm 1: - computation of $p_{t,c}$ defined using all loss estimates up to t-1, but there are no loss estimate for half of them. - 2(L/2) is confusing

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

2 fair

Presentation

3 good

Contribution

3 good

Limitations

I hope that my question can be answered, so I could verify the correctness of the analysis.

Summary

The paper proposes an efficient contextual bandit algorithm in the cross-learning setting, introduced in Balseiro et al., in the case of contexts sampled from an unknown distribution and where losses are chosen adversarially. In contextual bandits, the learner only utilizes the reward associated with an action for the current context. In contrast, in the cross-learning setting, the learner also exploits the reward associated with different contexts, which results in regret bounds that are independent of the total number of contexts. This approach can be employed in scenarios where that extra information is actually available such as bidding in nontruthful auctions, multi-armed bandits with exogenous costs, or repeated Bayesian games with private types. The proposed algorithm results in an optimal regret bound of $\tilde{O}(\sqrt{KT})$, with $K$ the number of arms and $T$ the number of rounds, thereby closing the existing regret bound gap in the literature. Building upon this optimal regret bound, the authors derived nearly tight regret bounds for two applications: bidding in first-price auctions, and sleeping bandits with arbitrary stochastic arm availabilities. The proposed approach bypasses the existing challenges in extending cross-learning contextual bandit to the unknown distribution setting by: 1) constructing an estimator with an in-built upper bound on the expected sum 2) introducing a novel technique for scheduling the learning algorithm that removes the correlation between the empirical estimate of the unknown distribution and the actions chosen by the algorithm, which is an obstacle for employing concentration inequalities.

Strengths

The paper is well-written, and the setup is clear. The limitations for extending existing algorithms are clearly explained, and the approach employed to overcome them is novel. To the best of my knowledge, the authors' result is new and shows a clear improvement over the state-of-the-art for cross-learning contextual bandits with unknown distributions. Thus, I recommend acceptance.

Weaknesses

Although the paper is technically solid, the contribution seems incremental, and the actual impact of extending the work of Balseiro et al. to the unknown distribution setting is not entirely clear. The computational efficiency aspect of the algorithm is not compared with what seems to be the most obvious baseline, i.e., the algorithm of Balseiro et al. that tackles the unknown distribution case. Lastly, I feel that the paper could benefit from numerical experiments that support the derived theoretical results. L. 117: “the we begin” L. 161: “we’d” → “we would” L.152/159: $\widehat{f_{tk}}(p) = \frac{1}{t} \sum_{s=1}^{t} p_{tk}(c_{t})$ → $\widehat{f_{tk}}(p) = \frac{1}{t} \sum_{s=1}^{t} p_{sk}(c_{s})$ ?

Questions

How does the computational efficiency of Algorithm 1 compare to existing approaches?

Rating

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

Confidence

2: You are willing to defend your assessment, but it is quite likely that you did not understand the central 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

3 good

Contribution

2 fair

Limitations

The limitations of the proposed approach are not entirely clear.

AC response to rebuttal

Hello authors, Could you please give some details about how exactly you are planning to improve the write-up according to the reviewer's complaints? Thank you, the AC

AC response to rebuttal

Hello authors, One more clarification question for you: I don't understand the point regarding the algorithm having the same complexity as in Balseiro et al. Shouldn't your current paper present a more efficient algorithm? I thought the main contribution was the efficiency aspect. What am I missing here? Thanks, the AC