Robust Contextual Pricing

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.

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.

Via 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:

• $O(C d \log \log T)$ regret in the known-corruption setting (from the SOTA $O(C d^3 \log^2 T)$).
• $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)$).

Finally, 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.

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.

The paper studies contextual pricing under adversarially corrupted binary feedback.
In 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 $).
The 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.
The goal is to minimize regret — the cumulative revenue loss relative to the clairvoyant seller.

Known-$ C $ case.
The authors give a reduction that calls any uncorrupted contextual pricing algorithm as a black box.
Instantiating it with the best current algorithm of Liu et al. (2021) yields a regret bound:

$

O\left( (C+1)\, d \log \log T \right),
$

improving the previous

$

O\left( C\, d^3 \log^2 T \right)
$

bound of Krishnamurthy et al. (2020).

Unknown-$ C $ (upper bound $ U $ known).
Using a multi-layer update-probability schedule (à la Lykouris et al., 2018), they obtain:

$

O\left( (C + \log U)\, d \log \log T \right)
$

with high probability.

For the non-contextual case ($ d = 1 $), they prove that no deterministic algorithm can achieve $ O(C + d \log \log T) $ regret.
When $ C = \Theta(\log \log T) $, any algorithm incurs at least

$

\Omega\left( \frac{C^2}{\log C} \right),
$

demonstrating that robustifying pricing is inherently harder than robustifying $ \varepsilon $-ball contextual search.

For a cautious buyer — who may refuse bargains but never overpays — they design an
$ O(C + \log T) $ algorithm in the non-contextual case, matching their lower-bound order (up to $ \log \log T $ vs. $ \log T $).

Methodology
The 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).

1. On each context $ x_t $, all copies propose prices; the maximum is posted.
   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.

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

A potential-function analysis borrowed from Liu et al. (2021) then bounds the regret of each slowed-down copy, which transfers to the master algorithm.

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

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.