High Probability Bounds for Cross-Learning Contextual Bandits with Unknown Context Distributions

Authors: Ruiyuan Huang, Zengfeng Huang
Primary area: learning theory
Keywords: contextual bandits, cross-learning, high-probability bounds

Abstract:
Motivated by applications in online bidding and sleeping bandits, we examine the problem of contextual bandits with cross learning, where the learner observes the loss associated with the action across all possible contexts, not just the current round’s context. Our focus is on a setting where losses are chosen adversarially, and contexts are sampled i.i.d. from a specific distribution. This problem was first studied by  Balseiro et al. (2019), who proposed an algorithm that achieves near-optimal regret under the assumption that the context distribution is known in advance. However, this assumption is often unrealistic. To address this issue, Schneider & Zimmert (2023) recently proposed a new algorithm that achieves nearly optimal expected regret. It is well-known that expected regret can be significantly weaker than high-probability bounds. In this paper, we present a novel, in-depth analysis of their algorithm and demonstrate that it actually achieves near-optimal regret with $\textit{high probability}$. There are steps in the original analysis by Schneider & Zimmert (2023) that lead only to an expected bound by nature. In our analysis, we introduce several new insights. Specifically, we make extensive use of the weak dependency structure between different epochs, which was overlooked in previous analyses. Additionally, standard martingale inequalities are not directly applicable, so we refine martingale inequalities to complete our analysis.

Decision: reject
Reviewer scores: 5, 5, 8, 6, 6

Reviews and discussion:
<thread>
creation date:
1730682341151

thread_type:
official_review

<thread_object>
creator: reviewer_8ljp

<content>
summary:
The submission studies contextual bandits with cross learning. Previously, the existing regret bound held in expectation. The submission refines the regret analysis so that the regret bound holds with high probability. The main contribution is to show how the weak dependency structure can be exploited to solve a concentration difficulty in the previous analysis.

strengths:
- The submission points out the difficulty that prevents the previous work from achieving a bound with high probability (lines 167–176).
- Identify the weak dependency between epochs (line 386).
- Devise a new technique to solve the unbounded issue induced by the weak dependency (the treatment for the Bias5e them in lines 395–411).

weaknesses:
- (1) Section 3.2 contains several subtopics, such as the regret decomposition, the discussion of each decomposed term, and the analysis strategy for the challenging term. A better editorial layout would improve the readability.
- (2) The sentence “Notably, …” in line 111 is confusing. It seems unrealistic to be able to observe the loss for every context $c$. It also does not match the algorithm’s (Algorithm 1) behavior.

questions:
- (1) Is the concept class $C$ a finite set? If so, what is the reason for assuming a finite concept class $C$? Practically speaking, the contextual information would be like a vector in a compact set, as it is very unlikely to see two identical users.
- (2) Where is the variable in Theorem 1 that characterizes the property of $C$? How does this variable appear in the bound proved in this submission?
- (3) Could you please provide more evidence or further discussion of the applicability of the technique developed here so that we can better appreciate its potential?
</content>
</thread_object>

</thread>
<thread>
creation date:
1731016880828

thread_type:
official_review

<thread_object>
creator: reviewer_sstz

<content>
summary:
The paper studied adversarial context bandits in a special setting where the losses of arm $a_i$ could be observed under all contexts when the algorithm plays arm $a_i$. The goal, like in classical adversarial bandit problems, is to minimize the regret compared to the loss of the best arm in hindsight. The paper focuses on the setting where the loss sequence is adversarial and the context is stochastic with an unknown distribution. A recent work of SZ [NeurIPS’23] designed an algorithm with *expected* regret of $\tilde{O}(\sqrt{KT})$ in this setting, where $K$ is the number of arms. This paper conducted a renewed analysis of the algorithm in SZ  [NeurIPS’23], and the main result is that the algorithm could actually achieve $\tilde{O}(\sqrt{KT})$ with high probability.

The main technique of the paper is heavily influenced by the previous work of SZ [NeurIPS’23]. In a nutshell, the low-regret guarantee of the algorithm crucially relies on the concentration of unbiased estimation of $E_{c}[\ell_{t,c}(a)]$. Here, we cannot exactly compute the quantity since the distribution of the context is unknown. The key idea of SZ [NeurIPS’23] is to commit two steps for each EXP3 step and use one of them to estimate the distribution of the context. On top of that, this paper further utilized the weak dependency between epochs, and derived a martingale argument to get high-probability regret.

strengths:
In general, my opinion of this paper is positive. The paper appears to require a great deal of background to be able to parse. Despite this, I believe the paper did reasonably well in terms of explaining the existing work and its techniques. Getting high probability bounds in adversarial bandits usually requires some neat observations and technical steps. Although I’m not able to follow all the steps in the short time frame, I do think the paper contains some nice technical observations and ideas.

weaknesses:
Although I'm mostly supportive, I think I couldn’t strongly champion the paper due to the following reasons:
- The scope of contribution: although the paper does contain some neat technical observations, the contribution appears to be somehow incremental. After all, this is a new analysis of an existing algorithm, and the new analysis is not something that improves the previous bound (but instead is to get a high-probability bound). Again, I do acknowledge that such contributions are non-trivial. However, I do not think it’s enough for me to champion the paper.
- If the paper is going to be mainly accepted due to the techniques: then, I do not think the paper contains a substantial amount of new ideas. I appreciate the technical observations, and I agree that the steps are non-trivial. However, if the conceptual message is not as strong, and the merits of the paper mainly lie in the techniques, then the bar would inevitably be higher. 
- For a conference like ICLR, the lack of experiments could be an issue. I am *not* letting this affect my score since I often advocate learning theory papers. However, I do want to raise this point since it is common for ML conferences to ask for experiments.

questions:
- Should the definition of regret on page 3 be reversed? As in, you are subtracting the loss of the best arm with the loss of a policy, which should be a negative value (if with positive regret). This would change the decomposition of the regret on page 5 as well, but it seems nothing would affect the correctness.
- I think the full algorithm description of the algorithm in SZ [NeurIPS’23] (or some simpler version of the description) could be shown much earlier in the paper. This would be helpful for readers who are not familiar with the previous algorithm.
- Also, stating the main theorem in a preliminary section looks very non-standard to me. I’m not letting this affect my score, but please consider re-organizing this.
- The meaning of 'with high probability' was never explained in the paper -- as in, it could mean with probability $1-1/K$ or with probability $0.99$. I think your bound gives the former, and this should be stated explicitly.
</content>
</thread_object>

</thread>
<thread>
creation date:
1731054710221

thread_type:
official_review

<thread_object>
creator: reviewer_udyz

<content>
summary:
The paper studies cross learning in contextual adversarial linear bandits where the learner observes the losses of all contexts in each round. Recent work in Schneider et al. proposed an algorithm with a regret upper bound only in expectation. The paper studies the same algorithm and proves that the regret upper bound holds with high probability.

strengths:
- The paper proves a high probability lower bound which is stronger than the in expectation bound in the literature.
- The analysis uses a nice observation that the different epochs in the algorithm are only weakly dependent which enables to prove a small bound for the cumulative bias across all epochs
- While standard martingale inequalities cannot directly upper bound the cumulative bias, a novel technique is proposed to address this

weaknesses:
Can the reduction in [1] be used to map the multi-context to a single context problem? The technique is proposed for non-adversarial losses, however, the action set map from distributional to fixed should not be affected by that.
I understand that the paper only focuses on analyzing an existing algorithm. However, a comparison with such technique in the related work is needed to justify the use of such algorithm or suggest alternative techniques to address the problem.

[1] "Contexts can be cheap: Solving stochastic contextual bandits with linear bandit algorithms." The Thirty Sixth Annual Conference on Learning Theory. PMLR, 2023.

questions:
please see weaknesses
</content>
</thread_object>

</thread>
<thread>
creation date:
1731056506679

thread_type:
official_review

<thread_object>
creator: reviewer_nztq

<content>
summary:
This paper addresses the challenge of achieving high-probability regret bounds in the adversarial contextual bandit framework, where the learner encounters varying contexts and must minimize cumulative loss over time. The focus is on "cross-learning" contextual bandits, where learners can observe losses for all possible contexts, not just the current one. 

Results leverage weak dependencies between epochs and refine existing martingale inequalities, by exploiting interdependencies in observations. This analysis ultimately shows that the algorithm is effective in adversarial settings, even with unknown context distributions.

strengths:
The paper proposes a new look at an existing problem and provides a completely novel analysis in their work. The ideas and techniques proposed are completely new and can be of independent interest. This is particularly true for the martingale concentration result.

weaknesses:
See questions.

questions:
While the result is good, I am uncertain about its significance because neither the problem nor the algorithm proposed are new. There are no extensions of this result, no experiments. I am not sure if this is standalone result is significant enough to be published at a premier conference.
</content>
</thread_object>

</thread>
<thread>
creation date:
1731417267340

thread_type:
official_review

<thread_object>
creator: reviewer_naxm

<content>
summary:
The paper proposes an algorithm that achieves high probability regret bound (which is stronger than the expected regret bound) for the cross-learning contextual bandits under unknown context distribution by developing refined martingale inequalities.

strengths:
1. The paper clearly presents the challenging point with detailed technical expressions and the novelty of the analysis.

weaknesses:
1. The explanation is only focused on technical side without the explanation of the algorithm. I suggest authors to spend more time including more explanations and organizing the paper.

questions:
1. What is the intuition behind the algorithm?
2. How the indicator function $F_e$ resolves the unbounded martingale inequalties?
</content>
</thread_object>

</thread>
<thread>
creation date:
1732173268858

thread_type:
official_comment

<thread_object>
creator: authors

<content>
title:
The revised version of the paper

comment:
Dear Reviewers,

We sincerely thank all the reviewers for their valuable suggestions. Based on your feedback, we have restructured the paper, and the revised version has been uploaded. In the new version, we have made the following changes:

- **Section 1**: We added a *Technique Overview* subsection to provide a clearer explanation of our technical contributions. Additionally, we discussed the paper mentioned by reviewer uDyZ in this section and included the informal version of the theorem.  
- **Section 2**: The new Section 2 now focuses solely on the problem formulation. Specifically, we have completely removed the theorem statement from this section.  
- **Section 3**: A new Section 3 has been created, incorporating content from the old Section 2.2 and Section 3.1. This section provides a clearer explanation of the existing algorithm.  
- **Section 4**: The new Section 4 is a revised version of the old Section 3. It has been divided into three new subsections, each dedicated to addressing a specific technical issue, thereby improving readability. Notably, the formal version of the theorem is now included in this section.  

We sincerely thank the reviewers once again for their valuable feedback.
</content>
</thread_object>

</thread>


Metareview:
metareview:
This paper explores adversarial context bandits, specifically focusing on a scenario where the losses of each arm are observable under all contexts when the algorithm selects that arm. The objective is to minimize regret by comparing the algorithm's performance to the best arm in hindsight, similar to classical adversarial bandit problems. The study examines a setting where the loss sequence is adversarial and the context is stochastic with an unknown distribution.

A prior work by SZ (NeurIPS'23) introduced an algorithm that achieved expected regret in this setting, where the number of arms was a factor. The main contribution of this paper is a refined analysis of the SZ algorithm, demonstrating that it can achieve a much lower regret with high probability. The paper builds on SZ's approach, which hinges on the concentration of unbiased estimation of the loss, despite the unknown context distribution. SZ's key idea involves a two-step process for each EXP3 step, with one step dedicated to estimating the context distribution. This paper extends SZ's method by leveraging weak dependencies between epochs and incorporating a martingale argument to achieve high-probability regret bounds.

The paper provides a new analysis of an existing algorithm, focusing on obtaining high-probability regret bounds. While the technical observations are non-trivial, the contribution is incremental, as it does not improve prior bounds or introduce substantial new ideas. Reviewers highlighted that the paper's primary merits lie in its techniques, which, while appreciated, may not meet the bar for ICLR without a stronger conceptual message. Additionally, concerns were raised about the lack of experimental validation, unconventional organization (e.g., the placement of the main theorem in the preliminary section), and unclear definitions (e.g., "with high probability"). Although these issues do not compromise correctness, they detract from the paper’s clarity and impact, leading to hesitations about its suitability for acceptance. Based on the common consensus, therefore, I would recommend that the authors submit to the next suitable venue to address all the concerns once all the necessary modifications are incorporated.