Robust Contextual Pricing
Authors: Anupam Gupta
Guru Guruganesh
Renato Paes Leme
Jon Schneider
Venue: NeurIPS 2025 poster ()
Keywords: pricing
contextual search
corruptions
online learning
Primary area: theory
TL;DR: We provide improved upper and lower bounds for contextual pricing with adversarial corruptions.

Abstract: We provide an algorithm with regret $O(C d \log \log T)$ for contextual pricing with $C$ corrupted rounds, improving over the previous bound of $O(d^3 C \log^2(T))$ of Krishnamurthy et al. The result is based on a reduction that calls the uncorrupted algorithm as a black-box, unlike the previous approach that modifies the inner workings of the uncorrupted algorithm. As a result, it leads to a conceptually simpler algorithm.

Finally, we provide a lower bound ruling out a $O(C + d\log \log T)$ algorithm. This shows that robustifying contextual pricing is harder than robustifying contextual search with $\epsilon$-ball losses, for which it is possible to design algorithms where corruptions add only an extra additive term $C$ to the regret.

Robust Contextual Pricing
Anupam Gupta NYU and Google
Guru Guruganesh Google
Renato Paes Leme Google
Jon Schneider Google
Abstract
We provide an algorithm with regret OCCd log T) for contextual pricing with corrupted rounds, improving over the previous bound of O(d log"())) of Krishnamurthy et al. (2020). The result is based on reduction that calls the uncor- rupted algorithm as a black-box, unlike the previous approach that modifies the inner workings of the uncorrupted algorithm. As result, it leads to conceptually
simpler algorithm.
Finally, we provide a lower bound ruling out O(C + d log log T) algorithm. This shows that robustifying contextual pricing is harder than robustifying contextual search with e-ball losses, for which it is possible to design algorithms where corruptions add only an extra additive term to the regret.
Introduction
In the contextual pricing problem, the seller is learner who, in each round, gets different product described by a feature vector Tt, for which then posts a price pt. Typically, the buyer purchases the product if its valuation (which is function (x;)) of the feature vector, and priori unknown to the seller) above this price. All the seller observes, after posting the price, whether the buyer purchases the product not. The goal of the learner (i.e., seller) is to maximize their revenue E, Pt (item sold). As usual pricing problems, the learner faces the exploration/exploitatii trade-off: it can "explore" by setting aggressive prices that allow it to learn about the buyer's valuation, but then it risks losing the sale; or it can "exploit" by setting conservative prices that guarantee a sale, but potentially get suboptimal revenue. In the revenue management literature, this is referred to as the learn-and-earn problem.
Such pricing problems pose two main challenges:
(i) we only observe binary feedback (sale or no-sale), but do not directly observe the loss in each round;
iii) the loss function is asymmetric and discontinuous: while under-pricing an item by amount x will result a sale with loss x with respect to the best possible revenue, over-pricing will cause the buyer not to purchase the produce and incur large constant loss.
For the single-dimensional non-contextual version of this problem, the seminal paper of Kleinberg and Leighton (2003) identifies the best way handle this asymmetry, obtaining the optimal regret of Olog log J.. Since then, the Kleinberg and Leighton (203) paper has been extended to the d-dimensional contextual case by a series of papers that have obtained increasingly better bounds: the work of Cohen et al. (2016) gave (d log T', Leme and Schneider (2018) showed O(d log log T"), and finally Liu al. (202T) gave Od log I'), matching the lower bound.
So far, our discussion has described the realizable and noise-free version of the problem: the buyer has fixed value v4, which is constant in [0 in the non-contextual case, linear function ve (xx)) = (v", _ra) in the contextual case. Moreover, the purchasing decision is based on whether the posted price pe is above or below this value u, There has been considerable work extending the
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

model to handle stochastic noise models: see, e.g., e.g..JJaaanni Javanmard and Nazerzadeh (2016); Cohen et al. (2016): Javanmard (2017): Shah et al. (2019) Liu al. (2021 Xu and Wang (2021 (022).
Comparatively, adversarial noise models (also known as corrupted feedback) are much less under- stood. The study of corrupted feedback for contextual pricing was pioneered by Krishnamurthy et al. (2020). In this model, there is still a ground truth value 2t and the buyer again makes most of the purchasing decisions based on whether pt I vt. However, for a certain number of rounds C, the decisions are arbitrary. This can model that buyers often make irrational choices (as in Krishnamurthy al.. (2020) or that an adversary can corrupt the feedback given to the learner in Lykouris et al. (2018 8
Paes Leme et al. (0022) )
1.1 Our Results
We give improved algorithms and lower bounds for the contextual pricing problem in settings with corrupted feedback.
Upper Bounds. Our paper proposes reduction from corrupted to uncorrupted case in contextual pricing and through that, obtains conceptually simpler algorithms with improved regret. Our results are the following:
Our Results:
1. For the known corruption setting, We give an algorithm that achieves regret of
O(IC 1) d log T).
This improves over the O(Cd log T) bound of Krishnamurthy et al. 2020
2. For the setting of unknown corruption C with a known upper bound U (i.e., we are promised that the actual number of corruptions C' is at most U), we give algorithm with regret
O((C + log U) . dog logglogT) T))
This improves over the regret bound of O((C log Uyd log T) given by Krishnamurthy et al. (2020).
At a high level, our approach to execute several parallel copies of an uncorrupted contextual pricing algorithm and query each of them in each round for advice on which price to set, choosing the maximum of such prices to post. In the case of sale, we choose a random algorithm the pool to update. We set the update probabilities in way that one of the parallel copies will never observe a corruption with high probability. The final step is to bound the regret of the entire algorithm by comparing it with the regret of the instance that never observes corruption.
The main observation is to exploit the following property of the pricing loss: if we choose the maximum price and it results in sale, the loss incurred it at most the loss of any given algorithm. This allows us charge the loss of the multiple algorithms maintained by our algorithm the loss of the benchmark, i.c., the single optimal algorithm that observes uncorrupted feedback.
Our Results: Lower Bounds. The lower bound the regret for the uncorrupted case is lo log T), so the best regret bound one can hope for is O + d log log 7). For the related problem of contextual search with e-ball loss (i.e., with different loss function), PPes Leme al.) (022)) show a regret bound of O(C + dllog(1fe)) which adds only an additive C overhead with respect the tight bound of (dd (ollg(L/)) for the uncorrupted case. The natural question is: can we hope to achieve algorithms with regret O(C + d log log T')?
In Theorem 5.2 we show this is not possible: we give a lower bound ruling algorithms with regret O + log log T), and hence showing that robustifying contextual pricing is harder than robustifying other contextual search problems (e.g., for the e-ball loss function).
These lower bounds also inspire new algorithmic results: using the ideas the lower bound, we are able to provide in Theorem 6.1 O + log -regret algorithm for the corrupted non-contextual case when corruptions are one-sided: i.e., the adversary allowed to corrupt no-sales to sales but not the other way round.
2

---

1.2
Related Work
Our paper lies in the intersection of the literature learning to price, contextual search, and learning with corrupted feedback. Learning to price was initiated by Kleinberg and Leighton (2003) who provide matching upper and lower bounds for the regret achievable by a seller posting prices to buyer under different assumptions the buyer's valuation. This setting was later extended to auctions Mohri and Medina (2014); Resa-Biaachh et al. (2014) and strategic agents Aggint//Aminn et al. (2013):
Drutsa (2017).
Contextual pricing is generalization of learning to price to higher dimensional settings, which is part of a larger class of problems known as contextual search which explore binary feedback in higher dimensional settings for various loss functions. A long line of paper starting with (mmin et al. (2014) provide increasingly better bounds for contextual search with the pricing loss and other types of losses: Cohen et al. (2016); Lobel et al. (018); Leme and Schneider (018); Liu et al. (2021).
Finally, learning with corruptions correspond to the study of settings in which the data follows predictable pattern with the exception of few examples whose label is arbitrary. very early example is called Ulam's 's game (Ulam (1976)) in which a learner tried to identify a number on sorted list using comparison queries but C' of those queries can have erroneous answers. Upper and lower bounds to this setting were given by Rivest et al. (1978).
There has been recent interest in providing corruption robust bounds contextual search problems. This was pioneered by Krishnamurthy et al. (2020) who study contextual pricing in the presence of corruptions the exact same setting as in our paper. Recently, Paes Leme et al.) (2022) studies the contextual search problem under the symmetric and e-ball losses with corrupted feedback.
Model and Definitions
(Uncorrupted) Contextual Pricing In the contextual pricing problem, the buyer's valuation is represented by vector v² By = {ir E R | 1] that is unknown the learner. In each round 1, I...T, T, the learner will be presented an item described by a feature vector 2, E and will have the opportunity
a price p. for the buyer. In the standard (un-corrupted) model, the buyer buys the value (u", xx) 2 Pt in which case the learner obtains revenue Pti otherwise, if the value (u", (.)) Pt then the buyer doesn't buy, in which case the learner obtains revenue zero. As usual, the learner is faced with the trade-off of proposing aggressive prices to learn more information about v², and setting conservative prices that will be guaranteed sell and generate revenue. To summarize, the feedback o, E {0, } and the loss E, are given by:
oe 1f 2 pc)
(e v.) d:Pt
for 21 = Od T)) on the total loss
Liu et al. 2021 recently showed matching upper and lower bounds of
>, l (also referred to as the regret) which is a contextual ver-
sion of the algorithm of Kleinberg and Leighton (2033).
Corrupted Feedback In the corrupted version of this problem, the learner has access to feedback o, {0,1), 1}. The corruption level C' is defined be the number of periods for which the feedback doesn't match 1 1(u, 2 j.j.i.e.
C= [T]: # 1f,, 2 pc})
In the known corruption case, the algorithm is given access to C. In the unknown corruption case, the algorithm knows an upper bound U on C' (c.g.. U = T in the worst case), and the regret bounds can depend on both (the actual corruption), and on (the upper bound, idcally logarithmically or better).
Note that we will still use the term regret to refer to the total loss Σ, & in the corrupted setting (with the sum ranging over all rounds f, even those with corrupted feedback). This deviates slightly from the definition of regret employed in Krishnamurthy et al.] (2020), which only counts losses in uncorrupted rounds note, however, that both notions of regret differ by at most C and hence do not affect any of the obtained asymptotic regret bounds (which even at best have some additive dependence on C)..
3

---

3 Reduction in the Known-Corruption Setting
We will present reduction from the uncorrupted setting to the corrupted setting for contextual pricing. In this reduction, we will treat the uncorrupted algorithm as a black-box described by two subroutines: (uery(æ:+) which returns a price Pr and Update (2t, Pt; ot). Given those subroutines, the uncorrupted algorithm can be described as follows:
(i) Query(x;) returns a price pr and doesn't I modify the internal state of the algorithm; (ii) the learner posts price pt and observes feedback oN (iii) Update Tt, Pr, στ) updates the state of the algorithm.
Given algorithm defined by Query(Iz) and Update(21, Pt, Pt. σz) and q 00, 1] we define its g-slowed-down version as the algorithm that prices according to Query(zz) but only calls Update (2, Pt, ot) with probability qi 2 9 upon receiving feedback. With remaining probabil- ity the state the algorithm is unchanged.
Theorem 3.1. If there exists an uncorrupted algorithm with loss at most R(T) such that:
1. its suggested price results in most R(T) no sales
2. the loss of its g-slowed-down version is at most R(T)/q
then there exists an algorithm with total loss at most O(C-R(T) in the corrupted setting with known corruptions.
Algorithm Description. We instantiate C' + 1 copies of the uncorrupted algorithm denoting the i-th copy by (azr) and Update,(ar: Pt, ot). We also maintain a set of active instances that is initially (1.2...., 13. Now, for each = 1...I . we:
obtain the price proposed by each algorithm Pt,: Query, (zt).
choose the largest price maxiga to post.
observe feedback de.
if o, (no-sale), let i E A be the index such that Pt Pt. Then call Update, (It, Pt, oz). If the i-th algorithm was updated with more than R(T) no sales, then remove i from the active set A.
if 1 (sale), then let be random index from A and call Update, (x,, (Ir. Pe. o1).
Proof. First we observe that there is at least one index 1" that never observes a corruption, hence the guarantees of the uncorrupted algorithm apply to it. By the first assumption in Theorem 3.1 this algorithm is never eliminated from the the active set.
To bound the total loss, we first observe that the total loss from periods which resulted in no-sale is most (C' + 1)T(T) since each copy of the algorithm can generate at most R(T) no-sales until eliminated.
Now, bound the total loss from periods in which there price Pt resulted in a sale, then the price under i' would also have resulted in a sale since pt, S Pt and furthermore, the loss E(pr; Ut) S. e Uz). Hence, the expected loss from the periods resulting in sales can be upper bounded by the loss of a IC+ -sloeed down version of the copy i' of the algorithm which (C + 1) R(T).
sale, observe that if the maximum
3.1 Analysis of the Slowed Down Algorithm
To conclude the proof, we show that the uncorrupted algorithm of Liu et al. (222 satisfies the conditions of properties in Theorem 3.1 We start by giving an overview that procedure:
Summary of the algorithm of Liu et al. 20011) The algorithm keeps a set S, C B of vectors consistent with the feedback observed so far. It also keeps A = log log T potential functions
$ (S.). ..... (S,) associated with the doubly-exponentia intervals J, [1/22' 11/22 for j > 1 and 7 = [1/4, 1] for j = 1. The potential functions depend only on the set S..
In each round i, the algorithm computes the width width(S;;
(ax(e, xz) min (v, x2)
wES,
vES,

---

If the width is below 1/T, the algorithm prices at the lower bound min (v, mz) guaranteeing sale with loss most 1/T. Otherwise, we choose an index j such that (idth(S,; 24) ) E In. The
algorithm then chooses price Pt function of j. St and and update the set St to
S {u E S (2o; (), xx) - pt) 2 0}
if there is a sale, then the loss is at most (i, = O(1/2²) and the j-th potential decreases by (S((++1) I (1 - )(1/22)) (),())(+))))))))) The remaining potentials weakly decrease.
if there is sale, then the loss is most 1 and the j-th potential decreases by oy(S++1) S 011/22)) ()(()1)). The remaining potentials weakly decrease.
Finally, the potentials are such that
, 2 1/2
which bounds the number of possible sales and no-sales for width(S 2 1/7. In particular, there can be at most
N (d d22"-1 + +2++2-1)
sales and
N == Ogd (/dlogd/2'-1 d/2'-1 +
no-sales whenever the width is in the interval I5. This leads to the overall bound of
(1/22)) N₃ OOd log log T + d llogd)
Lemma 3.2. The uncorrupted algorithm of Liu et al. 2027 satisfies the properties in Theorem 3.1 for R(T) Od log T + ddoggd)
Proof. The first property is trivially satisfied since no-sales accounted loss of 1 in the analysis above. Now, to analyze the g-slowed down algorithm we can keep the same potentials &, (S,) with the difference that they updated with probability q. The time between two updates of each potential is geometric random variable with probability So the expected number queries with width 1y with sale is Nj./q. /.. for N defined above in the algorithm summary. The total loss from sales is therefore at most /4) 1/22² in expectation. The lemma follows from the fact that
Σ NJ 1/22" s OOddlog log T + d log
by the analysis of the uncorrupted algorithm.
4 Sianownn-Corrpttion Setting
Here we assume that we have only an upper bound U on the number of corruptions, i.e., we know that C' < U but don't 't know the value of C. We provide algorithm that depends linearly C' (the actual corruptions) but only logarithmically on U. The ideas will be to use a version of the multi-layer approach of Lykouris et al. (2018). in which O(log U) copies of the original uncorrupted algorithm are run in parallel and each copy is updated with exponentially smaller probability. The copies in which the update probability is smaller than 1/C are unlikely experience corruption.
[o, 1], we instantiate & = log(U/5) copics of the uncorrupted algorithm denoting the i-th copy by Query, (x:) and Update, (1,, Pt, Pr,, dt). We also maintain a set active instances A that initially (1,2..... k... Now, for each = 1 we:
Algorithm Description For a parameter
obtain the price proposed by each algorithm Pt. Query,
choose the largest price Pt maXieA Pt,i to post.
observe feedback
5

---

if or 0 (no-sale), let i E A be the index such that Ps = Pt.é- Then call Update, (Ze, Pt, ot). If the i-th algorithm was updated with more than R(T) no sales, then remove all indices smaller or equal to from the active set A.
if ai = 1 (sale), then choose index i with probability 1/2 and call Update, (ze. Pt, 0z).
We note that the algorithm only differs from the known-corruption case in the probabilities used to update each algorithm. Also note that with non-zero probability we update algorithm that is no longer active. Such update is clearly useless, but we do so in order to preserve the probability that the still-active algorithms are updated.
Theorem 4.1. Given an uncorrupted algorithm wiht regret R(T) following the assumptions of Theorem 3.1Jand and known upper bound U on the (unknown) level of corruption C, there for every > 0, there exists an algorithm that with probability - 5 has total loss at most ((C//5) - log(U/6)) R(T)).
Proof. Let 1" be the index such that C/(26) S 2" S C/8.. For each corrupted round we update 8" with probability O(8/C). Across all the rounds, the probability it experiences no corruption is (1 (1- ( 1 - With that probability, this algorithm never eliminated from the active set A and the bounds from the uncorrupted algorithm will hold.
We again bound the total loss of sales and no-sales separately. Since each algorithm can incur at most R(T") no sales before it is eliminated, the total loss from no-sales is at most log(U/8) R(T)..
To bound the loss from sales, observe that if the maximum price resulted in sale, then Pt..* P must also result in a sale, so the loss is at most the loss of the loss of a (8/C)-slowed down version of the uncorrupted algorithm with is at most (C/6) R(T).
5 Lower Bound
We will study lower bounds for the special case of d = 1 in which the valuation is scalar and is non-contextual. This is the original setting of Kleinberg and Leighton (200)). The lower bound for the uncorrupted pricing problem is S2(log log T). The best upper bound we can hope for (even with known number of corruptions C) O log log T). The following lemma rules out this bound by
reduction to the lower bound for the online product design problem given by Eimamjomeh-Zadel
ct al. (021).
Theorem 5.1. No deterministic algorithm for the one-dimensional contextual pricing problem with (known) corrupted feedback can guarantee total loss at most OC + log log T). In particular, when C' C= Olog log T). any deterministic algorithm must incur least (CC² / log C') total loss.
We will prove Theorem 5.1 via reduction to the previously studied problem of online product design by [Emamjomehh Zadeh et al. (02II. Online product design is a variant of contextual pricing where there are different possible items, each with an unknown (one-dimensional) true value E [o, 1]. At each round E [7]. the learner can choose an item i, [d] and set a price Pt E [0, 1] for this item. If P: Vs., the item sells at this price and the learner obtains revenue Pt. otherwise the item goes unsold and the learner obtains revenue 0. The learner would like to minimize their regret compared to their optimal strategy, which is to always select the item i" with the largest value u. and price it at its value.
Emamjomeh-Zadee et al.] (2021) present an algorithm for this problem (a parallelization of the algorithm of Kleinberg and Leighton| (2003) that incurs at most O(n log log regret. More relevantly for us, they show that this multiplicative dependence is necessary by establishing the following lower bound.
Theorem 5.2 (Theorem 8 of [Emamjomehh Zadeh al. (2021) ). If n deterministic algorithm for online product design must incur [ logg n) regret in the worst case.
O(log OlogloogT) log then any
We will show that it is possible to reduce the problem of online product design to the problem of contextual pricing with corruptions. In particular, we will show that any algorithm for contextual pricing with C corruptions can be applied to get an equivalent regret bound in the C-item online product design problem.

---

Lemma 5.3. If there exists deterministic algorithm incurring at most R(C.T) regret for the contextual pricing problem with C corruptions, then there exists a deterministic algorithu incurring at most R(C,T T) regret for the online product design problem with C + 1 items.
Proof. Consider the following algorithm for online product design (that uses the corrupted contextual pricing algorithm as a black box). At any point it will maintain a state consisting of n + 1 numbers: [0, 1], the lowest price that any item has ever sold for, and yt, 92..... M/ [o, 1]. where y! is the highest price that item has not successfully sold for. Initially, x is initialized to 0 and all y: are initialized
The algorithm repeats the following procedure for T steps:
1. Choose an item i E arg max4e[n] ys with maximal unsold price.
2. Ask the corrupted contextual pricing subroutine for query price Pt.
3. Post price Pr for item iz.
4. If item is sells at this price, update max(x,,))) and report that the item sold to the
contextual pricing subroutine.
5. If item it fails to sell at this price, update yı, < min(ys, Pt), and report that the item failed to sell to the contextual pricing subroutine.
We first argue that the feedback provided to the contextual pricing subroutine over the course of this process must be consistent with some valid transcript contextual pricing with at most C corruptions. In particular, let Y be the maximum value of all at the end of the T rounds, and consider the scenario where the true value of the item in the corrupted contextual pricing subroutine is equal to Y - (for an arbitrary small >> O guaranteeing Y - 6 æ)). We claim this is consistent with all but at most n loss of generality that Y is the value of yı at the end of I' rounds. We claim that any other item can fail to sell at a price below Y at most once once it does so, it updates its y to a value below Y. and would only be picked over Y1 once y1 drops below Y (which it never does). Since there are n = C' other items, there are at most C' such events like this, which would constitute corrupted observations reported to the contextual pricing subroutine. On the other hand, since remains below throughout this process, we never report an error in the other direction (a sale at a price above Y), and hence these the only such corruptions.
C observations reported this subroutine. To see this, assume without
The regret of the corrupted contextual pricing subroutine under this scenario given by
(Y -)-
Σ oerr.
where, before, we write o, 1 if the item sells and a, 0 otherwise. But now, note that the maximum value of any item the optimal product design instance is at most Y, so the regret incurred by the online product design algorithm is at most
YT
diP--
It follows (by taking + 0) that any regret bound R(T) for the corrupted contextual pricing subroutine extends to this algorithm for online product design.
Proof of Theorem 5.1 Follows immediately from Theorem 5.2 and Lemma 5.3
7

---

6 One Sided Error: the Cautious Buyer
Finally, we use the ideas of the lower bound to derive an algorithm with regret O + log for what we call an "cautious buyer", which is buyer who may not buy even if the price is below their value but at most C times. The buyer never buys above their value. This corresponds to corrupted setting with one-sided corruption: d; I 1 1(2, pt)-
As in the previous section, we will state and prove this result in the non-contextual setting where the buyer's valuation can be expressed by scalar v² E [0.
Theorem 6.1. There is learning algorithm for posting a price to an cautious buyer (one-sided corrupted feedback with at most C' corruptions) with regret O(C + log 7).
The theorem will use the algorithm by Kirkpatrick and Gao (1990) to for the following problem: consider a list of numbers [v1,..., ma]. all in [0, 1J, unknown to the learner. The learner can at each time i choose an index 4, and price pt and query whether pi, I Us. The goal of the learner is to identify an index and price p such that: e2 2 2 max; i - c. Kirkpatrick and Gao (KG) provide an algorithm to acomplish this task with O(n + log(1/e)) comparisons.
Proof. Apply the KG algorithm find the maximum of a list of C++ numbers with parameter c = 1/T. For every query pi, u; of the KG algorithm, respond with the result of query P: U² to the corrupted contextual pricing algorithm. Because the buyer is cautious, the buyer may not buy a product even though the price below v" hence the feedback for some items in the list will be consistent with a value S V² since the KG algorithm only queries prices above the last sale and below the last no-sale for each item. For at least one of the items, however, the algorithm won't observe corruption, so it will be able to identify the o* within a margin of E = 1/T in O + log T) rounds. In such rounds, it will incur that much regret. From then on, the algorithm will incur at most O(1/T) regret per round.
Open Problems We note that the lower bound in Theorem
5.2 applies to the cautious buyer as well, hence it is not possible to improve this bound to O(C + log log T). However, we leave as an open question whether a bound of O(C + log T) is possible for buyer with corruptions in either direction. Another interesting open direction is to provide a O(C + dlog T) algorithm for cautious buyer in the contextual setting.
References
Amin, K., Rostamizadeh, A., and Syed, U. (2013). Learning prices for repeated auctions with strategic buyers. Advances in neural information processing systems, 26.
Amin, K., Rostamizadeh, A., and Syed, U. (2014). Repeated contextual auctions with strategic buyers. In Advances in Neural Information Processing Systems 27: Annual Conference on Neural Information Processing Systems 2014, December 8-13 2014, Montreal, Quebec, Canada, pages 622-630.
Cesa-Bianchi, N., Gentile, C., and Mansour, Y. (2014). Regret minimization for reserve prices in second-prie auctions. IEEE Transactions on Information Theory, 61(1):599-564
Cohen, M. C., Lobel, I., and Paes Leme, (2016). Feature-based dynamic pricing. In Proceedings of the 2016 ACM Conference Economics and Computation, pages 817-817. ACM.
Drutsa, A. (2017). crrizzonindependenn optimal pricing in repeated auctions with truthful and strategic buyers. In Proceedings of the 26th International Conference World Wide Web, pages 33-42.
Emamjomeh-Zadee E.,, Leme, R. P., Schneider, J., and Sivan, B. (2021). Jointly learning prices and product features. In IJCAI, pages 2360-2366.
Javanmard, A. (2017). Perishability data: dynamic pricing under varying-coefficie models. The Journal of Machine Learning Research, 18(1):1114-1744.
8

---

Javanmard, A. and Nazerzadeh, H. (2016). Dynamic pricing in high dige-simesssons. Working paper, University of Southern California.
Kirkpatrick, D. G. and Gao, F. (1990), Finding extrema with unary predicates. International Symposium Algorithms, pages 156-164. Springer.
Kleinberg, R. and Leighton, T. (2003). The value of knowing demand curve: Bounds regret for online posted-price auctions. Foundations of Computer Science, 2003. Proceedings. 44th Annual IEEE Symposium on, pages 594 605. IEEE.
Krishnamurthy, A., Lykouris, T., and Podimata, C. (2020). Corrupted multidimensional binary search: Learning in the presence of irrational agents, arXiv preprint arXiv:2002.11650
Leme, R. P. and Schneider, J. (2018). Contextual search via intrinsic volumes. In 59th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2018, Paris, France, October 7-9, 2018, pages 268 268-282.
Liu, A., Leme, R. P., and Schneider, J. (2021). Optimal contextual pricing and extensions. In Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithmss (SODA), pages 1059- 1078.
Lobel, I., Leme, R. P., and Vladu, A. (2018). Multidimennional binary search for contextual decision- making. Operations Research, 66(5): 1346-136..
Lykouris, T., Mirrokni, V., and Paes Leme, R. (2018). Stochastic bandits robust to adversarial corruptions. In Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing. pages 11--122.
Mohri, M. and Medina, A. M. (2014). Learning theory and algorithms for revenue optimization in second price auctions with reserve. In International conference on machine learning, pages 262-270. PMLR.
Paes Leme, R., Podimata, C., and Schneider, J. (2022). Coruption-robust contextual search through density updates. In Conference on Learning Theory, pages 3504-3505. PMLR.
Rivest, R. L., Meyer, A. R., and Kleitman, D. J. (1978). Coping with errors in binary search procedures (preliminary report). In Proceedings of the tenth annual ACM symposium Theory of computing, pages 227-232.
Shah, V., Johari, R., and Blanchet, J. (2019). in Neural Information Processing Systems, 32.
dynamic contextual pricing. Advances
Ulam, S. M. (1976). Adventures of Mathematician. Univ California Press.
Xu, J. and Wang, Y.-.. (2021). Logarithmic regret in feature- ceature-based dynamic pricing. Advances in Neural Information Processing Systems, 34.
Xu, J. and Wang. Y.-.. (2022). Towards agnostic feature-based dynamic pricing: Linear policies linear valuation with unknown noise. arXiv preprint arXiv:2201. 1341.

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: Yes, this theoretical paper in which all the claims are backed by mathemat- ical proofs.
2. Limitations
Question: Does the paper discuss the limitations the work performed by the authors?
Answer: [Yes]
Justification: We provide open problems making explicit the questions that are fully solved by the paper.
3. Theory assumptions and proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
Justification: We provide proofs to all the claims and checked them to the best of our abilities.
4. Experimental result reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided not)?
Answer: [NA]
Justification: No experimental results.
5. Open access to data and code
Question: Does the paper provide open access the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [NA]
Justification: The paper does not include experiments requiring code.
6. Experimental setting/details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [NA]
Justification: The paper does not include experiments.
7. Experiment statistical significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [NA]
Justification: The paper does not include experiments.
8. Experiments compute resources
Question: For each experiment, does the paper provide sufficient information the puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Answer: [NA]
Justification:
The paper does not include experiments.
10

---

9. Code of ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics httph//www....o.o.............tr
Answer: [Yes]
Justification: Theoretical research with ethics red flags.
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [Yes]
Justification: More efficient marketplaces and pricing can lead positive societal effects. Since it is mostly a theoretical investigation on an abstract setting, we believe the societal impact tangential.
Safeguards
Question:
Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Answer: [NA]
Justification: The paper poses such risks.
12. Licenses for existing assets
Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [NA]
Justification: The paper does not use existing assets.
13. New assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification: The paper does not release new assets.
14. Crowdsourcing and research with human subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include full text of instructions given to participants and screenshots, if applicable, as well as details about compensation (if any)?
Answer: [NA]
Justification: The paper does not involve crowdsoureing nor research with human subjects. 15. Institutional review board (IRB) approvals or equivalent for research with human subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/review based the requirements of your country institution) were obtained?
Answer: [NA]
Justification: The paper does not involve crowdsourcing nor research with human subjects.
Declaration LLM usage
Question: Does the paper describe the usage of LLMs if is an important, original, or non-standard component of the core methods in this research? Note that if the LLM is used only for writing, editing, formatting purposes and does not impact core methodology, scientific rigorousness, originality of the research, declaration is not required.
11

---

Answer: [NA]
The core method development in this research does not involve LLMs as any important, original, or non-standard components.
Justification:
12


Reviews:
[{"review_id": "YV60Vtmc5y", "reviewer": "Reviewer_uZ1C", "summary": "The paper studies contextual pricing under adversarially corrupted binary feedback.  \nIn each round \\\\( t \\\\in [T] \\\\), a seller observes a feature vector \\\\( x_t \\\\in \\\\mathbb{R}^d \\\\) that describes the product, posts a price \\\\( p_t \\\\in [0,1] \\\\), and observes only whether the buyer purchases (\\\\( \\\\sigma_t = 1 \\\\)) or not (\\\\( \\\\sigma_t = 0 \\\\)).  \nThe buyer’s latent valuation is assumed linear: \\\\( v_t = \\\\langle v^\\\\star, x_t \\\\rangle \\\\), but the feedback can be arbitrarily corrupted in at most \\\\( C \\\\) rounds.  \nThe goal is to minimize regret — the cumulative revenue loss relative to the clairvoyant seller.\n\n**Known-\\\\( C \\\\)** case.  \nThe authors give a reduction that calls any uncorrupted contextual pricing algorithm as a black box.  \nInstantiating it with the best current algorithm of Liu et al. (2021) yields a regret bound:  \n\\\\[\nO\\\\left( (C+1)\\\\, d \\\\log \\\\log T \\\\right),\n\\\\]  \nimproving the previous  \n\\\\[\nO\\\\left( C\\\\, d^3 \\\\log^2 T \\\\right)\n\\\\]  \nbound of Krishnamurthy et al. (2020).\n\n**Unknown-\\\\( C \\\\)** (upper bound \\\\( U \\\\) known).  \nUsing a multi-layer update-probability schedule (à la Lykouris et al., 2018), they obtain:  \n\\\\[\nO\\\\left( (C + \\\\log U)\\\\, d \\\\log \\\\log T \\\\right)\n\\\\]  \nwith high probability.\n\nFor the non-contextual case (\\\\( d = 1 \\\\)), they prove that no deterministic algorithm can achieve \\\\( O(C + d \\\\log \\\\log T) \\\\) regret.  \nWhen \\\\( C = \\\\Theta(\\\\log \\\\log T) \\\\), any algorithm incurs at least  \n\\\\[\n\\\\Omega\\\\left( \\\\frac{C^2}{\\\\log C} \\right),\n\\\\]  \ndemonstrating that robustifying pricing is inherently harder than robustifying \\\\( \\\\varepsilon \\\\)-ball contextual search.\n\nFor a cautious buyer — who may refuse bargains but never overpays — they design an  \n\\\\( O(C + \\\\log T) \\\\) algorithm in the non-contextual case, matching their lower-bound order (up to \\\\( \\\\log \\\\log T \\\\) vs. \\\\( \\\\log T \\\\)).\n\n**Methodology**  \nThe key idea is to run \\\\( C + 1 \\\\) (or \\\\( \\\\lceil \\\\log U \\\\rceil \\\\)) parallel copies of a standard uncorrupted learner (e.g., the Liu–Leme–Schneider 2021 algorithm with \\\\( O(d \\\\log \\\\log T) \\\\) regret).\n\n1. On each context \\\\( x_t \\\\), all copies propose prices; the maximum is posted.  \n   This ensures that a sale implies every other copy’s price was also acceptable, allowing one to charge the loss of the master algorithm to (essentially) the best uncorrupted copy.\n\n2. Update rules are randomized so that, in expectation, at least one copy receives no corrupted feedback, yet every copy is slowed down by at most a factor \\\\( O(C) \\\\) (or \\\\( O(C / \\\\delta) \\\\) in the high-probability version).\n\nA potential-function analysis borrowed from Liu et al. (2021) then bounds the regret of each slowed-down copy, which transfers to the master algorithm.\n\nThe lower bound reduces online product design with \\\\( n \\\\approx C \\\\) items (Emamjomeh-Zadeh et al., 2021) to contextual pricing with \\\\( C \\\\) corruptions, showing that an additive \\\\( C \\\\) price for robustness is unachievable.", "questions": "Same as weakness", "limitations": "Same as weakness", "rating": 4, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 4, "significance": 2, "originality": 3, "strengths_and_weaknesses": "**Strengths**  \nThe paper offers a clean and modular algorithmic framework that black-boxes any uncorrupted learner, leading to easy implementation and broad applicability.  \nIt significantly improves regret bounds by reducing their dependence on both dimension \\\\( d \\\\) and corruption level \\\\( C \\\\), and it sharpens theoretical understanding through matching lower bounds.  \nThe black-box reduction paradigm has potential to inspire similar techniques in other contextual decision problems with binary feedback.  \n\n**Limitation**  \nI greatly appreciate the paper’s clear presentation and its solid theoretical foundation. My main reservation concerns the model’s practical applicability. Could you please provide concrete examples or application domains in which this type of pricing problem naturally arises?\n\nIn addition, it would be very helpful to include numerical experiments that benchmark the proposed algorithms against established methods in the literature. Such results would illustrate the empirical effectiveness of your approach and strengthen the paper’s practical contribution.", "was_revised": true, "final_justification": "Dear AC and authors,\n\nAfter reading all the comments and responses, I am leaning slightly toward acceptance, given the contribution in tightening the upper bound. My concern about the true meaningfulness of the model remains, but I feel this should not detract from its contribution to the literature.\n\nBest wishes,\nYour reviewer", "rebuttal": "We thank the reviewer for their encouragement and suggestions. We are happy to hear that you liked the modular and conceptually clean framework for robust learning; indeed, we too feel this has broad potential. Below, please find responses to your comments.\n\n**Empirical Results and Relevance of our algorithm:** Although the focus of our paper was purely theoretical, the problem itself is well-motivated by practical considerations. In many settings when sellers are offering a set of differentiated products to a variety of users, they can determine the price of each item by trying to understand the market value for each of its intrinsic features. For example, [LPLV18] and [CLPL19] both use AirBnb or online advertising as examples of such a phenomenon. We will definitely consider empirical validation in our future work."}, {"review_id": "bWv9GEFv0t", "reviewer": "Reviewer_NBbZ", "summary": "The paper studies (noise-free) contextual pricing under adversarial corruptions. Specifically, in at most $C$ corrupted rounds the adversary can show to the learner an arbitrary feedback. The paper provides an algorithm with regret $O((C+1)d\\log\\log T)$ in the case in which $C$ is known upfront, and an algorithm with regret $O((C+\\log U)d\\log\\log T)$ for the case in which only an upper bound $U$ on $C$ is known. The paper also provides a negative result showing that no deterministic algorithm can guarantee a regret of $O(C+\\log\\log T)$ in this setup (even when knowing $C$ in advance). Finally, the paper provides an algorithm guaranteeing regret $O(C+\\log T)$ in the case in which the adversary is only allowed to change the feedback of no-sales to sales.", "questions": "can you clarify the relation between the corruption model you consider and that of Krishnamurthy et al., and comment on the precise notion of regret you’re considering?", "limitations": "yes", "rating": 3, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 2, "significance": 3, "originality": 2, "strengths_and_weaknesses": "I think the paper potentially has a set of interesting results but should be improved along several directions. \n\nFirst, the relation of the corruption model with those of prior works is not entirely clear. For instance, the paper repeatedly compares its results to those of Krishnamurthy et al.. However, the corruption model in Krishnamurthy et al. seems to be different from what is considered here: in their paper the adversary can manipulate the valuation, while here the adversary can only manipulate feedback. I would appreciate a more detailed discussion of the corruption model of Paes Leme et al. 2022 as well. Moreover, guarantees of Krishnamurthy et al. hold in high probability with respect to the realised losses, while from my understanding the guarantees provided in this paper hold only in expectation. \n\nRelated to the last point above, I think the paper could benefit from a rewriting in which details of the results are formally spelled out. As it is, it feels a bit handwavy in certain points (e.g., in theorem 3.1 what’s the notion of regret you’re actually bounding?). \n\nThe lower bound provided in the paper is for deterministic algorithms, but the algorithms presented are all randomised. It would be nice to have a characterisation for the same class of algorithms (or at least some discussion about that). I guess part of the problem here is using the result on online product design as a blackbox. \n\nSection 6 is lacking many details: does the learner need knowledge of $C$ in Theorem 6.1? What is the algorithm mentioned at line 282 supposed to do? It would also be nice to add some further comments on why one sided errors make the problem fundamentally easier. \n\nThe reference for Krishnamurthy et al. should be updated since it is referring to an old version of the paper.", "was_revised": true, "final_justification": "Updated score to reflect clarifications from the authors.", "rebuttal": "We thank the reviewer for their questions and suggestions. We are glad that you found the results interesting, and we are happy to clarify some confusions, and hope that these will remove your concerns about our work, and make your evaluation more positive.\n\n**Relationship of Our Model to [KLPS20]:** The model used in our paper and that of Krishnamurthy et al. are essentially the same, despite cosmetic differences in how they appear. \nBoth the models are concerned with the number of corrupted rounds, and both of them bound this number by $C$. \nIn the [KLPS20] model, the adversary can manipulate the loss incurred during a corrupted time-step, whereas our adversary can corrupt the feedback. Since there are only $C$ corrupted rounds, this changes the true loss by at most O(1), since the losses are bounded. \nTherefore the difference between the losses of the two models is at most an *additive* term of $O(C)$. Since both algorithms must suffer at least $\\Omega(C)$ regret, the regret is essentially the same under both models up to constant factors. We will definitely add a discussion about this to the paper. \n\n**Notion of Regret:** The notion of regret that we minimize (it is also defined in line 105) is to minimize the sum of the losses. We will edit the paper to make this more clear, and also work on the rest of the paper to make the presentation more transparent.\n\n**Randomized vs Deterministic Algorithms:** Understanding what is possible in the corrupted setting with fully deterministic algorithms (or conversely, proving lower bounds that apply to randomized algorithms) is an interesting future direction. Despite this mismatch, we still feel that the lower bound we establish in Section 5 is valuable by providing some evidence that a multiplicative $C$ factor is required.\n\n**Details in Section 6:** Thanks for pointing this out, we will definitely clarify the setting of Section 6. In that section, the learner does know the total number of corruptions $C$ (or at least, an upper bound on this). Moreover, the Kirkpatrick-Gao algorithm mentioned in line 282 solves the following problem: find the maximum of $C$ real numbers in [0, 1] to within precision $\\epsilon$ using only $C + \\log(1/\\epsilon)$ threshold queries (of the form, “is $x_i > v$” for given $i \\in [C]$ and $v \\in [0,1]$). We will reword and emphasize this in the revised version."}, {"review_id": "PYYZNoyJqH", "reviewer": "Reviewer_8XkP", "summary": "This paper studies the problem of robust contextual pricing. At round $t$, the seller can propose a price $p_t$, and is reported whether $v^* \\cdot x_t \\ge p_t$ (in which case the seller gets revenue $p_t$) or not (in which case the seller gets revenue $0$). However, there will be $C$ rounds where the feedback to the seller is corrupted.\n\nVia a reduction to the uncorrupted case (specifically, to algorithms in the uncorrupted case that exhibit \"slowdown-able\" and \"many-sales\" properties), this paper was able to improve the following upper bounds:\n- $O(C d \\log \\log T)$ regret in the known-corruption setting (from the SOTA $O(C d^3 \\log^2 T)$).\n- $O((C + \\log U) d \\log \\log T)$ regret in the unknown-corruption-with-known-upper-bound setting (from the SOTA $O((C + \\log U) d^3 \\log^2 T)$).\n\nFinally, the paper showed that any algorithm must incur a regret of $\\Omega(C + d \\log \\log T)$, via a reduction to a lower bound for the related *online product design* problem.", "questions": "1) Do you think the right answer for this model would be $\\Theta(C d \\log \\log T)$ or $\\Theta(C + d \\log \\log T)$, or somewhere in between? In other words, do you think the $C$ multiplicative factor incurred for robustifying is necessary, or are there different ways to reduce the corrupted case to the uncorrupted case, or other techniques that one can do to mitigate this loss?", "limitations": "yes", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 4, "clarity": 4, "significance": 4, "originality": 3, "strengths_and_weaknesses": "**Strengths**:\n- The results are conceptually simple and clear, yet it improves the state-of-the-art by quite a large margin. Specifically, the reduction to the uncorrupted setting is easy to understand and only incurs an additional $C + 1$ loss in multiplicative factor, so one can simply verify-and-plug the state-of-the-art uncorrupted algorithm to obtain near-optimal bound.\n- The paper is well-written, and the proofs provided (seem to) have no issues.\n\n**Weaknesses**:\n- A very minor weakness of this paper would be that the lower bound and upper bound is still not matching, but I would not put too much weight on this at all.", "was_revised": true, "final_justification": "I have read the rebuttals and decided to keep my score.", "rebuttal": "We thank the reviewer for their encouragement and suggestions, and we are happy that you enjoyed the paper.\n\nThe question you ask (of whether the multiplicative factor incurred for robustifying is necessary, or if  there are other ways to mitigate this loss) is a great question! Indeed it is one that we hope to make progress on, and address further in future works. Please note that the lower bound we establish in Section 5 provides some indication that this multiplicative factor is necessary—in particular, the lower bound says that any *deterministic* algorithm must incur the multiplicative factor, and so if we want to improve, we must look at randomized algorithms."}, {"review_id": "IkXncVgRSf", "reviewer": "Reviewer_9M6Y", "summary": "The paper studies a version of contextual pricing robust to corruption. The buyer's valuation is represented by $\\langle v*, x_t\\rangle$ and the purchase decision depends on whether $v_t \\geq p_t$ - the price - or not. The purchase decision represents the learner's available feedback. In the setup here, the corruption budget $C$ represents how many times the buyer can deviates from the expected purchase decision. To prove their upper-bound, that outperforms the state-of-the-art, the authors rely on $C+1$ copies of an uncorrupted contextual pricing algorithm that they update specifically in order to handle corruption. They also show that the uncorrupted algorithm proposed by Liu et al. 2021 satisfies the required assumptions and can be used as a subroutine. Finally, they extend their setup to encompass the unknown-corruption setting and prove a lower bound.", "questions": "I understand that the paper is mostly theoretical but do the authors know if there is empirical evidence for the use of corrupted pricing algorithm?", "limitations": "As said in the weaknesses, the limitation is mostly about the broad impact of the work, which appears as quite niche - although interesting - to me.", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 4, "significance": 3, "originality": 2, "strengths_and_weaknesses": "I believe that the main strengths are:\n\n- the paper is very clear and easy to read.\n\n- the proposed method based on replicata of an uncorrupted pricing algorithm to deal with the corruption is elegant and efficient.\n\n- their method outperforms the existing bounds for this setup.\n\nThe main weaknesses are:\n\n- the setup studied in the paper is not new and already exists, which diminishes the novelty of the work.\n\n- the question tackled by this work is quite niche because it consists of a method that only applies to corrupted contextual pricing and very close scenarios. It is interesting but quite narrow.", "was_revised": true, "final_justification": "I am in favor of acceptance and hence, I maintain my score.", "rebuttal": "We thank the reviewer for their comments and suggestions, and we are happy that you enjoyed the paper. \n\nRe: whether there is empirical evidence for the use of corrupted pricing algorithms, online contextual pricing in the presence of noise is a practical problem arising in many different settings (where real algorithms are designed and run to address this problem). We view this work as providing a theoretical foundation for this problem in a (relatively) assumption-free / worst-case setting.  See also our response to the first reviewer."}]

Author rebuttal:

Meta-review: The paper studies contextual pricing with linear valuations that might be corrupted. At each round in the uncorrupted case, the learner observes a $d$-dimensional feature vector $x_t$ for the item being sold, and the buyer's valuation is $x_t^T v^\*$ for some unknown $v^\*$. The learner sets a price, and the buyer decides to purchase the item if their valuation exceeds the price. The learner only receives feedback on whether a purchase occurs and aims to set prices that maximize its cumulative revenue. In the corrupted case, an adversary can alter the feedback observed by the learner in up to $C$ rounds. The authors prove an upper bound of $O(Cd\log\log T)$ when $C$ is known and $O((C+\log U)d\log\log T)$ if $U$ is an upper bound on $C$, thus improving the existing upper bound of $O(Cd^3\log^2 T)$. They also prove a lower bound for deterministic algorithms, showing that no algorithm can guarantee a bound of $O(C+\log\log T)$. Finally, they provide an algorithm that achieves a regret of  $O(C+\log T)$ when the adversary can only switch no-sales to sales.

The reviewers all appreciated the proposed algorithmic approach and the improvement in the upper bounds compared to existing algorithms. The main concern raised by the reviewers regards the lower bound - both due to the gap from the upper bound and the fact that it only holds for deterministic algorithms (whereas the algorithm in the paper is randomized). Despite these concerns, the overall contributions, particularly the improved upper bounds and the establishment of the first lower bound for this problem, led me to recommend accepting the paper.

The reviewers also identified several issues related to clarity and the connection of this model to prior work. The authors are asked to revise the text to address these points in accordance with their rebuttal.
Decision: Accept (poster)