acceptodds
Withdrawn from ICLR 2027

Cross-learning for performative prediction with changing objectives.

Withdrawn from ICLR 2027, so left out of the paper lists and the map.

Abstract

We study contextual performative prediction, where, given side information, a learner repeatedly chooses a model to deploy and incurs a context-dependent loss. Deploying a model influences the distribution of the resulting outcomes, but this influence is independent of the current context. Consequently, observing the outcome of deploying a model in one context also provides information about its behavior in other contexts. We formalize this structure through continuous-armed bandits with cross-learning and introduce the cross-context zooming dimension, a new complexity measure that captures the difficulty of learning across contexts. We establish a lower bound on the regret in terms of this dimension and design matching algorithms, first for the general cross-learning setting and then tailored to contextual performative prediction.

Primary area:
learning theory
Keywords:
performative prediction, bandits, cross learning, dynamic pricing

Reviews

Among:
Shape:
1234this paper, Bottom 10%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 1.67 over 3 reviews, above 10% of the others.
Reviewer_jk6pOpenReview ↗
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 ctc_t, the learner chooses an action θt∈[0,1]D\theta_t\in[0,1]^D, observes Zt∼D(θt)Z_t\sim\mathcal D(\theta_t), and suffers a context-dependent loss ℓct(Zt,θt)\ell_{c_t}(Z_t,\theta_t). The distribution map is assumed to be unknown, context-independent, and ϵ\epsilon-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 O~(Td+1d+2)\widetilde O(T^{\frac{d+1}{d+2}}), while Theorem 2 gives a matching-in-TT 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:

  1. They have a well-motivated formulation. The reduction from contextual bandits with performative feedback (CBPF) to contextual bandits with cross-learning (CBCL) is nice.

  2. 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.

  3. The lower-bound construction is also good. The paper uses familiar assumptions, including ϵ\epsilon-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:

  1. 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.

  2. 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.

  3. I think the phrase “for TT 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” ϵLz\epsilon L_z also needs justification.

  4. 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 DD.

Questions for authors

Here are the questions for the authors. If they are addressed, I am willing to raise my score.

  1. What regret does uniform discretization combined with Balseiro et al. (2019)’s cross-learning UCB achieve in this setting?
  2. What is the explicit threshold underlying “TT large enough” in Theorem 3? Please state its dependence on ϵLz\epsilon L_z, α\alpha, DD, and LθL_\theta, and clarify what guarantee applies below that threshold.
  3. If the distribution shift is small, how should the Theorem 3 guarantee be affected?
  4. Since the grid resolution and horizon condition involve LθL_\theta, in what sense does the bound depend only on ϵLz\epsilon L_z? Is LθL_\theta required as an input to construct the grid? I might have overlooked if this was stated somewhere.
  5. Can Theorem 2 be extended to instances whose cross-context dimension is strictly smaller than the ambient dimension?
1 comment

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 TDD+2T^{\frac{D}{D+2}}, and running this algorithm on the resulting TDD+2T^{\frac{D}{D+2}}-armed bandit with cross learning, would result in a regret of order O~(TDD+2T)=TD+1D+2\tilde{O}(T^{\frac{D}{D+2}}T) = T^{\frac{D+1}{D+2}}. 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, TT should be large enough to verify the following inequalities: j0=⌊log⁡2((T/64αβLd)1d+2)⌋≤log⁡2(0.8T6L)−1j_0 = \left\lfloor\log_2\left((T/64\alpha\beta L^d)^{\frac{1}{d+2}}\right) \right\rfloor \leq \log_2\left(\frac{0.8\sqrt{T}}{6L}\right) - 1 for β=log⁡(2(3+D)T)\beta = \log(2(3+D)T) ensures that the discretization error remains negligible (proof of Lemma 4, page 30, line 1027). This requires TT to grow linearly in L4d+1L^{\frac{4}{d+1}}. More precisely, using β>1\beta>1, it requires that T≥(6Le0.8(64αLd)−1d+2)2(d+2)d+1T\geq \left(\frac{6Le}{0.8}\left(64\alpha L^d\right)^{\frac{-1}{d+2}}\right)^{\frac{2(d+2)}{d+1}}. Moreover, to absorb the bonus β=log⁡(2(3+D)T)\beta = \log(2(3+D)T) into the absolute constant CC (in line 764), we need to be able to write, e.g., log⁡(2(3+D)T)≤2log⁡(T)\log(2(3+D)T)\leq 2\log(T), which is true if T≥2(3+D)T \geq 2(3+D). We will state this more clearly in the appendix.

For Theorem 3 to hold, TT should verify T≥D(Lθ+ϵLz)2T \geq D(L_{\theta} + \epsilon L_z)^2 (see also our answer to Question 4) to ensure that the discretization error is negligible. Lemma 6 also requires T≥(D+1)/(ϵLz)T \geq (\sqrt{D}+1)/(\epsilon L_z) to bound the number of bins activated. Finally, to state our bound at the end of the proof (line 930), we must have i0=⌈1d+2log⁡2(5(ϵLz)2T33(4+2D)2Dαlog⁡(T))⌉≥1i_0 = \left \lceil \frac{1}{d+2}\log_2\left(\frac{5(\epsilon L_z)^2T}{33(4+2D)2^D \alpha\log(T)}\right) \right \rceil \geq 1, i.e. T/log⁡(T)≥33(4+2D)2Dα5(ϵLz)2T/\log(T) \geq \frac{33(4+2D)2^D\alpha}{5(\epsilon L_z)^2}. We will state this more clearly in the appendix.

Bellow these thresholds, no guarantee currently applies except the trivial bound RT≤TR_T \leq 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)2D(L_{\theta} + \epsilon L_z)^2 \lesssim T \lesssim (1/\epsilon L_z)^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\epsilon >0. When ϵ\epsilon is small enough so that the first level of bins is never de-activated (i.e., T≲(1/ϵLz)2T \lesssim (1/\epsilon L_z)^2), Lemma 7 implies Δ(θt,ct)≤5rt(Bt(θt))\Delta(\theta_t, c_t)\leq 5 r_t(B_t(\theta_t)) with high probability when T≥D(Lθ+ϵLz)2T \geq D(L_{\theta} + \epsilon L_z)^2 (necessary to bound the discretization error)(1). Classical arguments then imply that the regret in each bin is of order T\sqrt{T} (up to numerical constants and logarithmic factors), and since there is a finite number of bins in B1\mathcal{B}_1 the total regret is of the same order. Note that this T\sqrt{T} rate is expected, as when ϵ\epsilon 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+1d+2T^{\frac{d+1}{d+2}} (except when ϵ=0\epsilon = 0, where it is T\sqrt{T}, in which case there is not performative aspect to the prediction). Moreover, since the parameters ϵLz\epsilon L_z and TT are known to the agent, they can always choose, if T≤(1/ϵLz)2T\leq (1/\epsilon L_z)^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)2T = D(L_{\theta} + \epsilon L_z)^2 up to T=(1/(ϵLz))2T = (1/(\epsilon L_z))^2. The paper focuses on the regime T≥(1/(ϵLz))2T \geq (1/(\epsilon L_z))^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)T \geq (\sqrt{D}+1)/(\epsilon L_z) 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.

Reviewer_GzU4OpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper studies contextual performative prediction with changing objectives, where the loss function varies across contexts while the distribution map induced by the deployed decision remains unchanged. The authors formulate this problem through continuous-armed contextual bandits with cross-learning. The paper introduces the cross-context zooming dimension to characterize the complexity of near-optimal actions across different contexts. Based on this notion, the authors propose CL-ZOOMING and establish regret upper and lower bounds with matching dependence on the time horizon, up to logarithmic factors. The paper further develops ZOOC, which exploits performative feedback and decoupled risk estimation to obtain regret guarantees depending on the sensitivity of the distribution map rather than the full Lipschitz constant of the performative risk. The theoretical results are illustrated through an application to dynamic pricing with varying production costs. However, the paper does not provide numerical experiments or empirical comparisons with existing methods.

Critical strengths

The most interesting aspect of the paper is its attempt to characterize continuous-armed cross-learning problems through the geometry of near-optimal actions across contexts. The proposed cross-context zooming dimension offers a potentially useful perspective on why individually simple contextual learning problems may collectively exhibit greater complexity. The authors also provide a theoretical framework connecting changing objectives, cross-learning, and performative feedback. If the matching regret bounds are established rigorously, the complexity characterization could constitute a meaningful theoretical contribution. However, my overall assessment is limited by concerns about the incremental novelty of the proposed methods and the correctness of important parts of the theoretical analysis.

Critical weaknesses
  1. The incremental methodological and theoretical contributions over existing literature are insufficiently established. My first concern is that the proposed algorithms largely combine established techniques, while the paper does not sufficiently demonstrate which aspects of the resulting guarantees fundamentally exceed prior work. CL-ZOOMING appears to integrate the classical zooming algorithm for continuous-armed bandits with the cross-learning feedback structure introduced by Balseiro et al. (2019). The resulting algorithm retains the familiar confidence-based action selection and activation rules, while using observations collected under different contexts to estimate rewards. In particular, the worst-case regret rate of order O~(T(D+1)/(D+2))\widetilde{O}(T^{(D+1)/(D+2)}) can already be obtained by discretizing the continuous action space and applying existing finite-armed cross-learning methods, assuming Lipschitz rewards. Therefore, the main potential contribution of CL-ZOOMING lies in the finer instance-dependent characterization through the cross-context zooming dimension, rather than the general worst-case rate or the algorithmic structure itself. Although this complexity measure is potentially interesting, the paper does not sufficiently explain its relationship to existing zooming dimensions and instance-dependent regret analyses, or establish why the proposed characterization cannot be obtained through existing analytical frameworks. A similar concern applies to ZOOC. Jagadeesan et al. (2022) already established how performative feedback and decoupled risk estimation can yield regret guarantees depending primarily on the sensitivity of the distribution map rather than the full complexity of the loss function. ZOOC combines this principle with recursive partitioning and cross-context information sharing. However, the paper does not provide a sufficiently explicit comparison with the existing performative confidence bounds framework. In particular, it remains unclear what fundamentally new algorithmic or theoretical difficulty arises from combining these previously studied components, and whether ZOOC yields a provable improvement over suitable extensions of existing methods. The dynamic pricing example also provides limited support for novelty. Dynamic pricing with exogenously varying costs was already discussed as an application of cross-learning by Balseiro et al. (2019). Moreover, the reported T2/3T^{2/3} regret rate is consistent with what can be obtained through existing cross-learning methods combined with standard action-space discretization. Consequently, the paper's main theoretical innovation appears to rest heavily on the proposed cross-context complexity measure and its matching bounds. A substantially clearer distinction from prior work is necessary to establish the significance of this contribution.
  2. The proof of the central lower bound requires clarification and correction, while the proposed algorithms lack supporting validation. My second major concern relates to Theorem 2, which is central to the paper's claim that the proposed complexity measure characterizes the intrinsic difficulty of the problem. In Appendix B (page 16), the authors express the KL divergence between two problem instances as a sum of Bernoulli KL divergences evaluated only at the realized context ctc_t. However, the CBCL feedback model allows the learner to observe the reward process across all contexts after selecting an action. Therefore, the KL divergence between the complete observation histories generally cannot be computed using only the reward distribution associated with ctc_t. For example, an action selected under context c1c_1 may reveal information about the unknown reward structure associated with another context c2c_2. Such information must be accounted for in the KL analysis. The proof should explicitly specify the joint distribution of the cross-context feedback vector and establish a valid KL bound for the full observation process. The particular hard-instance construction may permit a corrected bound of the same order, but the equality currently used in Appendix B is not justified under the stated feedback model. There is also a problem in the proof of Lemma 5 (Appendix D.5, page 20). The proposed containment of the near-optimal set requires the distance from the optimal point xczcx_c^{z_c} to lie in an interval with a strictly positive lower endpoint. However, the optimal point itself has distance zero and necessarily belongs to the near-optimal set for every positive tolerance. Thus, the stated containment does not hold as written. Furthermore, Theorem 2 is stated for all real d≥1d \geq 1, whereas the proof constructs a DD-dimensional Euclidean action space with D=dD=d. This construction directly covers integer dimensions, but the argument for non-integer values of dd is not provided. These issues do not necessarily invalidate the lower-bound result, but they leave important gaps in the current proof of one of the paper's central contributions. Beyond these theoretical concerns, the manuscript provides no numerical experiments, baseline comparisons, or ablation studies. While experiments are not strictly necessary for a theoretical paper, their absence makes it difficult to assess whether the proposed methods yield meaningful advantages beyond their asymptotic guarantees. In particular, the paper does not demonstrate whether CL-ZOOMING can practically exploit instances with low cross-context zooming dimension, or whether ZOOC benefits from its performative-feedback-specific design compared with existing alternatives. Given that the algorithmic components are closely related to established methods, such comparisons would be particularly valuable for substantiating the claimed contribution.
Questions for authors
  1. What is the precise incremental contribution over existing cross-learning and performative feedback methods? Could the authors provide a more explicit theoretical comparison with Balseiro et al. (2019), classical contextual zooming methods, and Jagadeesan et al. (2022)? In particular, which guarantees cannot be obtained by combining existing cross-learning algorithms with standard discretization or existing performative confidence bounds? What genuinely new technical difficulties are resolved by CL-ZOOMING and ZOOC?
  2. How is Theorem 2 justified under the complete cross-learning feedback model? Could the authors clarify the joint distribution of the observed rewards across contexts and derive the KL divergence for the complete feedback history, rather than only the realized context? Additionally, could the authors correct the near-optimal set characterization in Lemma 5 and clarify how the lower-bound construction extends to non-integer values of the cross-context zooming dimension? A complete resolution of these issues is important for assessing the validity of the claimed matching bounds.
  3. Can the authors substantiate the practical or theoretical advantage of the proposed algorithms over existing alternatives? For CL-ZOOMING, it would be useful to demonstrate the benefit of the cross-context zooming dimension in instances where it is substantially smaller than the ambient dimension. For ZOOC, a direct comparison with existing performative confidence bounds methods, or an analysis isolating the benefit of cross-context information sharing and adaptive partitioning, would help clarify the contribution. The current dynamic pricing example establishes applicability under the stated assumptions but does not demonstrate a distinct improvement over existing approaches.
2 comments

We address the specific concerns of the reviewer below. However, we are particularly puzzled by the following statement (end of weakness 2): "the paper does not demonstrate whether CL-ZOOMING can practically exploit instances with low cross-context zooming dimension, or whether ZOOC benefits from its performative-feedback-specific design compared with existing alternatives." This is specifically what this paper is demonstrating in Theorems 1 and 3. We do understand that this is done through a number of technical arguments. We hope that in light of our responses below the reviewer will reconsider his judgement.

Question 1 We address the concerns raised by the reviewer regarding the novelty of our approach.

  • Novelty with regard to performative prediction: Prior work in performative prediction treats the loss function as fixed when designing algorithms for finding performative optima (e.g., Jagadesaan et al. (2022)). Our results are the first to study changing losses and discuss how information can be shared across different learning problems. Algorithms from prior work can not take advantage of this overlap. And they can also not be naturally extended, as we do not assume that the loss is regular with regards to the contexts. This would mean that you have to reinitialize the algorithm from scratch every time you change the loss. We argue that this is a practically relevant problem, as you might update the weighting of your data, or the regularization parameter as you go. Reinitializing the algorithm would mean to waste costly deployments by throwing away all the knowledge you have acquired previously. Our algorithm addresses this and quantifies what you can save with our new approach.

  • Novelty with regard to cross-learning: Zooming does not allow for contextual observations; running independent zooming algorithms on clustered contexts is not applicable, as we do not assume regularity of the reward function w.r.t. context. A natural benchmark for Lipschitz bandit with cross learning, pointed out by reviewer jk6P, would be to run the algorithm of Balseiro et al. (2019) on a discretized grid. Choosing a regular grid of size TDD+2T^{\frac{D}{D+2}} and running this algorithm on the resulting TDD+2T^{\frac{D}{D+2}}-armed bandit with cross learning would result in a regret of order O~(T−DD+2T)=TD+1D+2\tilde{O}(T^{\frac{-D}{D+2}}T) = T^{\frac{D+1}{D+2}}. 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. On the other hand, 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 dimension).

Question 1 We also clarify our technical contributions. Our main technical contributions are Theorem 2 and Algorithm ZOOC. Algorithm 1 follows from arguments developed to analyse the regret of ZOOMING and arguments used, e.g, by Balserio et al. to bound the regret of pulling a given action in multi-arm bandits with cross-learning; the main difficulty and technical novelty is, as noted by reviewer wk1c, that we not only need to control the number of actions that are almost optimal in some favourable context, but also to account for the fact that in other contexts these actions are sub-optimal (leading us to define our sets Θ~i\tilde{\Theta}_i and Θi\Theta_i, and the rounds Ti(θ)\mathcal{T}_i(\theta) -- see lines 690-746 of our proofs).

  • Theorem 2: As noted by the reviewer, providing a lower bound under cross-learning is intrinsically more difficult than without cross-learning, as an action provides information in all contexts (not just the current one). When considering K-armed bandits under cross-learning with fully connected feedback graph, the worst-case upper bound is the same as in classical K-armed bandit, and so the lower bounds for K-arm bandits hold. By contrast, in our setting the regret upper bound is distinct from the upper bound in the non-contextual case (a phenomenon that is new in cross-learning): the lower bound precisely establishes that the problem may be easy for each context independently, but lead to a high regret overall. Proving this requires designing hard instances that reflect this phenomenon, and are completely new. It also requires handling dependence between observations in a new fashion: even though in the hard instance, the set of action is partitioned into disjoint bins, with each bin being optimal for a specific context, we cannot treat this problem as ∣CT∣\vert \mathcal{C}_T\vert independent bandit problems, as the strategy may choose to sample action in a sub-optimal bin, thus acquiring information useful for a different context. For these reasons, classical arguments treating each problem independently fail (using, e.g., Bretagnolle-Huber inequality along with a hammering argument), and we must rely on more involved arguments (here, we used a version of Fano's Lemma primarily used for estimation, and a Varshamov-Gilbert argument).

  • Algorithm ZOOC: A number of difficulties arise when considering cross learning in performative prediction. Compared to non-contextual performative prediction, optimal actions may change from one round to the next due to different contexts, and so the "phased elimination" approach of Jagadesaan et al. (2022) is obviously not applicable, as it requires to sample repeatedly the same action. This leads us to design an algorithm closer to ZOOMING. However, compared to Lipschitz bandit, the intrinsic difficulty when considering performative prediction arise from the fact that the reward function may have large variations within a confidence set. The size of the confidence set is chosen so that the error in estimating the decoupled performative risk stemming from the stochastic error and the (ϵLz)(\epsilon L_z)-Lipschitz fluctuations due to performative change in distribution are of the same order. Within this confidence set, the performative risk (with Lipschitz constant (Lθ+ϵLz)(L_{\theta} + \epsilon L_z)) may have large variations. In other words, we may know that some regions within a given confidence set are strongly sub-optimal compared to others, a phenomenon that does not appear in classical Lipshitz bandits. This has a very concrete consequence: we may be required to sample actions that are not the centre of their confidence set. As the number of observations grows, the radius of the confidence set should decreases, uncovering actions whose observations where used to estimate the reward within this confidence set... Technically, this implies that we need new ways of covering the space of actions. More crucially perhaps, we also need to account the fact that now some parts of a given confidence region are near-optimal, while some are strongly sub-optimal. On top of this, the contextual aspect of our problem implies that some actions are optimal in some contexts, but sub-optimal in others (as pointed out by reviewer wk1c). Our algorithm may refine its confidence set in a context where some of the actions covered may be optimal, but these actions may be strongly sub-optimal in the next contexts: in order to not blindly resample these actions and estimate their reward from scratch whenever their confidence set is refined, we must keep in memory our previous estimates. These difficulties are entirely absent from the context-free Phased Elimination algorithm of Jagadesaan et al., and from the original ZOOMING algorithm, and require new algorithmic solutions and technical arguments to be handled.

Reviewer_wk1cOpenReview ↗
Rating
1
Confidence
2
Informativeness
2
Presentation
2
Soundness
1
Read review
Paper summary

This paper studies contextual performative prediction with changing loss functions and a fixed distribution map. Since the distribution induced by a deployed model is independent of the current context, observations can be reused across objectives. The authors formulate the problem as a continuous-armed bandit with cross-learning and introduce the cross-context zooming dimension. They propose CL-ZOOMING and establish upper and lower regret bounds, followed by ZOOC, which exploits performative feedback to replace dependence on the full risk Lipschitz constant with dependence on distribution sensitivity. The results are theoretical, with dynamic pricing under changing production costs serving as an analytical example.

Critical strengths
  1. The distinction between changing objectives and a fixed distribution map is useful and well motivated. It provides a concrete basis for reusing observations across objectives, and the reduction to continuous-armed cross-learning makes this information-sharing structure explicit.
  2. The cross-context zooming dimension captures an interesting distinction between the geometry of near-optimal actions within individual contexts and that of their union. This perspective helps explain why low per-context complexity may not be sufficient to achieve low regret across contexts, although the claimed characterization requires the corrections discussed below.
Critical weaknesses
  1. The proof of Theorem 1 appears to omit part of the contextual regret. In Appendix A, lines 697–701, membership in Θ~j0\widetilde{\Theta}_{j_0} requires an action to be near-optimal in at least one context. However, line 726 sums only over Θ~j\widetilde{\Theta}_j for j<j0j < j_0. Let II denote the set of rounds satisfying both θt∈Θ~j0\theta_t\in\widetilde{\Theta}_{j_0} and Δ(θt,ct)>rj0\Delta(\theta_t,c_t) > r_{j_0}. The omitted contribution is

    Rmiss=∑t∈IΔ(θt,ct).R_{miss}=\sum_{t\in I}\Delta(\theta_t,c_t).

    Being near-optimal in one context does not control the gap in another: an action could satisfy Δ(θ,c1)=0\Delta(\theta,c_1)=0 and Δ(θ,c2)=1/2\Delta(\theta,c_2)=1/2. Thus, the definition does not imply that RmissR_{miss} vanishes or is bounded by Trj0Tr_{j_0}. This term requires a separate bound or a different regret decomposition.

  2. The lower-bound reward construction in Appendix B, lines 775–786, is not Lipschitz as written. Branch selection uses d∞d_\infty, while bump heights use d∞′d'_\infty, resulting in a discontinuity. Take D=2D=2, zc=+1z_c=+1, and

    θδ±=xc+ϵ(1/10,7/20±δ),0<δ<1/20.\theta_\delta^\pm=x_c+\epsilon(1/10, 7/20\pm\delta), \qquad 0 < \delta < 1/20.

    Substitution gives

    mz(θδ−,c)=12+ϵ82(310+2δ),mz(θδ+,c)=12−ϵ402.m^z(\theta_\delta^-,c) =\frac{1}{2}+\frac{\epsilon}{8\sqrt{2}} (\frac{3}{10}+2\delta), \qquad m^z(\theta_\delta^+,c) =\frac{1}{2}-\frac{\epsilon}{40\sqrt{2}}.

    Hence, the reward difference tends to ϵ/(162)>0\epsilon/(16\sqrt{2}) > 0, whereas ∣θδ−−θδ+∣=2ϵδ→0\\|\theta_\delta^--\theta_\delta^+\\|=2\epsilon\delta\to0. This contradicts Lemma 5 and Assumption 3. The construction may be repairable, but the current instance does not establish Theorem 2.

    The KL calculation in lines 823–826 also accounts only for the current-context reward, although the learner observes Mt=(Mt(c))c∈CT\mathbf M_t=(M_t(c))_{c\in C_T}. Under conditionally independent components, the relevant expression is

    KL(Pz,Pz′)=∑t=1T∑c∈CTEz[kl(mz(θt,c),mz′(θt,c))].KL(P_z,P_{z'}) = \sum_{t=1}^T\sum_{c\in C_T} E_z[ kl(m^z(\theta_t,c),m^{z'}(\theta_t,c)) ].

    The joint feedback law and the bound for the full observations need to be specified. A corrected construction might preserve the intended rate, but this requires verifying both the geometric and information-theoretic arguments.

  3. The grid in Theorem 1 does not support the stated uniform guarantee over LL. With one context, D=1D=1, G=⌈T⌉G=\lceil\sqrt T\rceil, and L=4GL=4G, consider the deterministic reward

    m(θ)=max⁡(0,1−L∣θ−1/(2G)∣).m(\theta)= \max(0,1-L|\theta-1/(2G)|).

    This function is bounded and LL-Lipschitz, with optimal reward 11 and reward 00 at every point of the prescribed grid. Thus, RT=TR_T=T. Nevertheless, Definition 2 holds with d=0d=0 and α=max⁡(25,12L+1)\alpha=\max(25,12L+1): for r<1/Lr < 1/L, ΘLr\Theta_{Lr} has length at most 2r2r, so its r/12r/12-packing number is at most 2525; for r≥1/Lr\ge1/L, the packing number of [0,1][0,1] is at most 12L+112L+1.

    Since α=O(T)\alpha=O(\sqrt T), the stated bound is O(T3/4log⁡T)O(T^{3/4}\sqrt{\log T}), contradicting linear regret. This concerns the uniform statement with an absolute constant, rather than the asymptotic rate for fixed LL. The theorem requires an explicit horizon restriction, an LL-dependent grid, or a discretization term.

  4. Theorem 3 leaves the required grid resolution unspecified, although its proof relies on particular grid properties in lines 1090 and 1113–1117. There is also a gap in the inequality at line 1121. Let a=ϵLzr(Pa(B))a=\epsilon L_zr(Pa(B)) and r=rt(B)r=r_t(B). Let D^\widehat D denote the child estimate and P^\widehat P the lower confidence bound for θ\theta in Equation (2). Equation (2) uses the child estimate when r≤2ar\le2a, but the proof claims

    PR(θ)−4min⁡(a,r)≤P^.PR(\theta)-4\min(a,r) \le\widehat P.

    The stated error event does not imply this inequality: a=0.1a=0.1, r=0.19r=0.19, PR(θ)=0.5PR(\theta)=0.5, and D^=0.45\widehat D=0.45 satisfy the error bound, yet

    P^=0.45−2(0.19)=0.07<0.5−4(0.1)=0.1.\widehat P =0.45-2(0.19)=0.07 < 0.5-4(0.1)=0.1.

    This proof step requires a corrected constant or an additional argument; it is not, by itself, a counterexample to the final regret rate.

    Two specification issues also require correction. Algorithm 2, line 10, reuses Bt\mathcal B_t after removing the parent, retaining it alongside its children. The update should remove the parent and add its children in a single operation. Additionally, the estimator's condition τ(B)≤s<t<τ′(B)\tau(B)\le s < t < \tau'(B) excludes all samples after deactivation; the stored parent estimate should instead use τ(B)≤s<min⁡(t,τ′(B))\tau(B)\le s < \min(t,\tau'(B)). A precise algorithm and revised supporting lemmas are needed to assess the guarantee.

  5. As a minor point, the paper includes no experiments. One or two synthetic settings would help illustrate the gains over learning separately in each context and the improvement of ZOOC over CL-ZOOMING. Varying distribution sensitivity and the overlap of context-specific optima would be informative. I do not consider experiments necessary for a theoretical contribution, but they would strengthen the illustration.

Questions for authors
  1. How is RmissR_{miss} controlled in the proof of Theorem 1? Could you provide a bound for this contribution or a corrected regret decomposition?
  2. Could you provide a globally Lipschitz lower-bound construction that preserves the required zooming properties? Could you also specify the joint cross-context feedback law and calculate the KL divergence for the full observations?
  3. Is Theorem 1 intended to hold only for fixed LL and sufficiently large TT? If so, what parameter-dependent horizon restriction is required? Otherwise, how should the grid or bound be modified?
  4. What grid resolution is required by Theorem 3? Could you correct the bin update and stored parent estimator, and justify or revise the inequality at line 1121, including its effect on the subsequent regret bound?
1 comment

The second concern can be resolved by defining Qc±Q_c^{\pm} as Qc+=x∈Qc:x⊤e1≥xc⊤e1Q_c^{+} = \\{x \in Q_c : x^{\top}e_1 \geq x_c^{\top}e_1\\} and Qc−=x∈Qc:x⊤e1<xc⊤e1Q_c^{-} = \\{x \in Q_c : x^{\top}e_1 < x_c^{\top}e_1\\} (where e1e_1 is the first vector of the canonical basis), so that Qc+Q_c^{+} and Qc−Q_c^{-} are the right and left halves of QcQ_c along the first axis.

The first concern, however, cannot be addressed without modifying the algorithm. To guarantee that actions are not activated when they are optimal simply to be chosen when they are suboptimal, the upper confidence bound would need to incorporate a memory effect, in the spirit of ZOOC. This would require changes to both the algorithm and the proof that go beyond what is reasonable for a rebuttal, and we have therefore decided to withdraw our submission. We thank the reviewer for their consistent engagement throughout the discussion.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Discussion (0)

Sign in to comment.