- Rating
- 2
- Confidence
- 3
- Informativeness
- 2
- Presentation
- 2
- Soundness
- 2
Read review
Paper summary
The paper studies contextual performative prediction, where the learner’s objective varies across rounds while the distribution map induced by its deployed model remains fixed. At each round, an oblivious adversary reveals a context , the learner chooses an action , observes , and suffers a context-dependent loss . The distribution map is assumed to be unknown, context-independent, and -sensitive in Wasserstein-1.
The authors reduce this problem to a continuous-action contextual bandit with cross-learning (CBCL), where an observation can be used to evaluate losses across contexts. They propose the algorithm CL-Zooming, which shares observations across contexts and adapts exploration to near-optimal actions. They introduce the cross-context zooming dimension to characterize the complexity of the joint problem. Theorem 1 establishes an upper regret bound of order , while Theorem 2 gives a matching-in- worst-case lower bound for CBCL. The lower-bound construction demonstrates that individual contexts can have uniform zooming dimension zero while their combined problem has positive cross-context dimension. The authors also delve into contextual bandits with performative feedback (CBPF). The authors propose ZooC, which recursively partitions the action space and uses decoupled performative-risk estimates to construct lower confidence bounds. The paper’s evaluation is entirely theoretical, with no computational experiments.
Critical strengths
The strengths are as follows:
-
They have a well-motivated formulation. The reduction from contextual bandits with performative feedback (CBPF) to contextual bandits with cross-learning (CBCL) is nice.
-
The complexity measure makes sense. The cross-context zooming dimension is a nice conceptual contribution. I think the key takeaway is interesting. In the worst case, cross-learning with Lipschitz rewards is no harder than non-contextual Lipschitz bandits, but per-context zooming dimensions can underestimate the difficulty of the joint problem.
-
The lower-bound construction is also good. The paper uses familiar assumptions, including -sensitivity in Wasserstein-1, Lipschitz losses, and an oblivious context sequence. It does not impose additional structural assumptions on the distribution map.
Critical weaknesses
The weaknesses are as follows:
-
The improvement over existing methods is not exactly clear. The paper compares CL-Zooming primarily against running Zooming independently in each context. This baseline ignores cross-learning, so outperforming it does not isolate the benefit of the proposed algorithm.
-
The complexity measure can be loose in certain cases. The cross-context zooming dimension is defined through a union of near-optimal action sets across contexts. This union does not account for how frequently a context appears or how much regret it can contribute. A context that appears only once can likewise enlarge the union, even though its total contribution to regret is bounded by a constant.
-
I think the phrase “for large enough” hides a horizon condition that depends on problem parameters, including the sensitivity-scaled constant. This needs to be made more explicit. The claim that the bound “depends only on” also needs justification.
-
I am not sure how tight the established bound is. The lower bound in Theorem 2 concerns CBCL, not CBPF. Its construction uses an ambient dimension aligned with the cross-context dimension, so it does not establish tightness in the regime where the cross-context dimension is substantially smaller than .
Questions for authors
Here are the questions for the authors. If they are addressed, I am willing to raise my score.
- What regret does uniform discretization combined with Balseiro et al. (2019)’s cross-learning UCB achieve in this setting?
- What is the explicit threshold underlying “ large enough” in Theorem 3? Please state its dependence on , , , and , and clarify what guarantee applies below that threshold.
- If the distribution shift is small, how should the Theorem 3 guarantee be affected?
- Since the grid resolution and horizon condition involve , in what sense does the bound depend only on ? Is required as an input to construct the grid? I might have overlooked if this was stated somewhere.
- Can Theorem 2 be extended to instances whose cross-context dimension is strictly smaller than the ambient dimension?
Thank you for the feedback. We address the individual questions below.
Question 1. The reviewer is right in underlining that another natural benchmark would be to run the algorithm of Balseiro et al. (2019) on a grid of actions. Choosing a regular grid of size TD+2D, and running this algorithm on the resulting TD+2D-armed bandit with cross learning, would result in a regret of order O~(TD+2DT)=TD+2D+1. Thus, when the cross-context zooming dimension is as large as the ambient dimension, our algorithm does not improve over this benchmark. The same phenomenon happens when considering non-contextual Lipshitz bandit, where when the zooming dimension is equal to the Lipschitz dimension, ZOOMING offers no advantage compared to running UCB on a grid. Conversely, CL-ZOOMING is able to adaptively take advantage of small cross-context zooming dimension to achieve lower regret (similarly as ZOOMING adaptively takes advantage of small zooming dimensions).
Question 2. For Theorem 1 to hold, T should be large enough to verify the following inequalities: j0=⌊log2((T/64αβLd)d+21)⌋≤log2(6L0.8T)−1 for β=log(2(3+D)T) ensures that the discretization error remains negligible (proof of Lemma 4, page 30, line 1027). This requires T to grow linearly in Ld+14. More precisely, using β>1, it requires that T≥(0.86Le(64αLd)d+2−1)d+12(d+2). Moreover, to absorb the bonus β=log(2(3+D)T) into the absolute constant C (in line 764), we need to be able to write, e.g., log(2(3+D)T)≤2log(T), which is true if T≥2(3+D). We will state this more clearly in the appendix.
For Theorem 3 to hold, T should verify T≥D(Lθ+ϵLz)2 (see also our answer to Question 4) to ensure that the discretization error is negligible. Lemma 6 also requires T≥(D+1)/(ϵLz) to bound the number of bins activated. Finally, to state our bound at the end of the proof (line 930), we must have i0=⌈d+21log2(33(4+2D)2Dαlog(T)5(ϵLz)2T)⌉≥1, i.e. T/log(T)≥5(ϵLz)233(4+2D)2Dα. We will state this more clearly in the appendix.
Bellow these thresholds, no guarantee currently applies except the trivial bound RT≤T. In the following question, we discuss guarantees that we can obtain for ZOOC in the regime where D(Lθ+ϵLz)2≲T≲(1/ϵLz)2 -- i.e., when the discretization error is still negligible, but the distribution shift can be ignored.
Question 3. Theorem 3 holds under the assumption that ϵ>0. When ϵ is small enough so that the first level of bins is never de-activated (i.e., T≲(1/ϵLz)2), Lemma 7 implies Δ(θt,ct)≤5rt(Bt(θt)) with high probability when T≥D(Lθ+ϵLz)2 (necessary to bound the discretization error)(1). Classical arguments then imply that the regret in each bin is of order T (up to numerical constants and logarithmic factors), and since there is a finite number of bins in B1 the total regret is of the same order. Note that this T rate is expected, as when ϵ is small enough, the problem effectively reduces to a continuous bandit with full information (the distribution can safely be considered static, and every sample can be used to estimate the reward of every action).
We did not discuss this regime in Theorem 3, as it is transient, and the asymptotic worst-case rate is effectively Td+2d+1 (except when ϵ=0, where it is T, in which case there is not performative aspect to the prediction). Moreover, since the parameters ϵLz and T are known to the agent, they can always choose, if T≤(1/ϵLz)2, to run an algorithm for risk minimization under full information (such as Follow-the-Leader). Our algorithm achieves the same regret rate over part of the transient regime, from T=D(Lθ+ϵLz)2 up to T=(1/(ϵLz))2. The paper focuses on the regime T≥(1/(ϵLz))2, where we believe the most interesting phenomena happen because Follow-the-Leader no longer suffices and more sophisticated algorithms are needed. If the reviewer thinks a discussion of the transient regime would be of interest to readers, we would be happy to include it in the revision.
(1) Note that T≥(D+1)/(ϵLz) is only used in Lemma 7 to bound the maximal depth of the bins that are activated and need to be counted in the union bound. When this depth is 1, this condition is not necessary, see lines 1077 - 1081.