Online Learning in the Repeated Mediated Newsvendor Problem

Is $U^{\sharp}_{k,i}(p)$ defined? We define the operator $\sharp$ that maps any USC function $u$ into its transformed $u^{\sharp}$ on line 52 of the main part of the paper, at the beginning of Section 1.2 (Formal setting). But the reviewer raises a good point that adding a reminder around line 903 would improve clarity, as the reader may have forgotten its definition by that point. We implemented this change for the revised version.

Typos on line 903. Thank you for catching it! The terms $1/K(K-j)$ and $1/Kj$ on line 903 are indeed typos and should both be $1/K^2$, consistently with the rest of the paper. We double-checked and didn't find any other occurrences of these typos. We updated the revised version with this change.

Assumption 1.3 has a missing "$m$". Thank you for catching this typo as well! Assumption 1.3 should indeed be "The cumulative distribution function (cdf) of the supplier’s cost $C$ is $m$-Lipschitz". In Line 895, we use precisely this assumption when we upper bound $\mathbb E [ \mathbb I$ { $p_j < C \le p$ } $]=\mathbb P [ p_j < C \le p ] \le m \cdot (p - p_j)$. We updated the revised version with this change.

Why few samples give $O(1/K)$-sized confidence intervals. The reviewer's intuition is roughly correct. For each price $p_j$, we have $K(K-j+1)$ samples for the term that involves $F_j$, and $K j$ samples for the term that involves $G_j$. As the reviewer's intuition suggested, for lower prices $p_j$, the terms $G_j$ are easier to estimate (since we are estimating the integral of a $[0,1]$-valued function in $[0,p_j]$), while for higher prices the terms $F_j$ are easier to estimate (since we are estimating the integral of a $[0,1]$-valued function in $[p_j,1]$). The trick to prove this intuition (see lines 927-930) is to apply Hoeffding's inequality to a slightly larger set of random variables, generated by adding identically-zero random variables until reaching a total of $K^2$ zero-mean, $[-\frac1K,\frac1K]$ independent random variables.

As a sanity check, notice that when $j = 1$ (resp., $j = K$), we are in fact using $K^2$ samples to obtain the order $1/K$ in the confidence interval for $F_1$ (resp. $G_K$).

Could the authors comment more about how more relaxed feedback models could potentially improve the regret rate? Intriguing question. A feedback of theoretical interest that is commonly considered is "full feedback". In our setting, this would mean that $C_t$ and $U_t$ are revealed at the end of each round. We make the following conjectures for this setting:

1. Independence of $C_t$ and $U_t$ is not necessary to guarantee learnability, and neither is Lipschitnzess of the cdf of $C_t$;
2. A follow-the-leader (FTL) approach should lead to a $\sqrt{T}$ regret guarantee. However, we suspect that some novel uniform convergence argument would be needed to obtain the $\sqrt{T}$ bound for FTL due to the specific complexities of the problem.

We hope our answers helped clarify all lingering doubts.

If this is the case, we'd kindly ask the reviewer if they would consider readjusting their score.

I thank the authors for their detailed response. I think most of my points have been addressed. Given that, I will maintain my current score and discuss further with other reviewers in later phases.

Is the USC assumption common? Good question. As far as we know, it is not a common assumption. To the best of our knowledge, the most common assumption by far is that utilities are (at least) Lipschitz. Our USC assumption is weaker (in fact, even strictly weaker than continuity alone) but still sufficient for our theory. In particular, all (possibly discontinuous) right-continuous non-decreasing functions are upper semi-continuous and can therefore be encompassed by our theory. We will highlight this in the revised version.

Does the model account for the average cost of unsold goods? If not, how does this cost impact the derived regret bounds? In our setting, goods are produced only after they are ordered. For instance, in online freelance marketplaces, freelancers only complete tasks, i.e. produce the "goods", after both the freelancer and the user agree to the job. Similarly, in ridesharing platforms, drivers only incur fuel/car maintenance costs during the ride, which occurs after an agreement is made between the driver and the rider. However, this is an interesting direction to explore for future work and we thank the reviewer for their suggestion.

Add error bars. We thank the reviewer for the suggestion. Please see our response to Question 3 of reviewer m1KJ (labeled by: Add error bar and statistical significance.) for a detailed explanation of how the updated plots will look like in the revised version.

Are our assumptions realistic? We thank the reviewer for raising this point and are happy to clarify.

As shown in Theorem 5.1, if any one of the assumptions is relaxed, sublinear regret is no longer achievable. Thus, under non-stationary dynamics or concentrated cost distributions (which violate Assumptions 1.1 and 1.3, respectively), the problem becomes unlearnable, regardless of the model.

That being said, an interesting direction for future work would be to explore relaxations of the problem setting. For example, the weaker benchmark of $\alpha$-regret may allow for learnability under non-stationary dynamics.

We also note that several real-world applications in which our assumptions are approximately satisfied are discussed in the motivations section. Please refer to our response to Question 1 of reviewer m1KJ (labeled by: Can you discuss your assumptions further?) for a more in-depth explanation of the real-world relevance of these assumptions.

We hope our answers helped clarify all lingering doubts.

If this is the case, we'd kindly ask the reviewer if they would consider readjusting their score.

Can we assume suppliers' costs are independent of retailers' utilities? Fair question. A first reason why the assumption is reasonable is related to the distinct economic drivers of suppliers and retailers. Supply‑side costs typically depend on factors like input prices, technology, scale, and logistics, whereas demand‑side utilities depend on consumer preferences, substitution patterns, and timing. These factors do not always overlap. For example, a fall in steel prices lowers bicycle-frame costs but does not necessarily change a commuter's willingness to pay for the bike.

Another reason is that in many mediated markets, the item traded is fixed (e.g., a specific SKU, ride, or room‑night). In this case, switching a supplier for another affects the production cost but not the retailer's valuation of that identical item. In other words, if it is always the same type of item that's traded, it is realistic to assume that the random draw of the supplier would not influence that of the retailer.

A more technical reason has to do with necessity (not mere convenience) for learnability. Theorem 5.1 shows that allowing any statistical dependence between $C$ and $U$ makes sublinear regret unachievable: the optimal benchmark itself becomes unidentifiable.

That said, if markets exhibit shared shocks (e.g., seasonal effects) that influence both $C_t$ and $U_t$, it could be natural to extend our proposed setting to a contextual setting where a context vector $x_t$ is available to the learner at the beginning of each round. This is an intriguing direction that, to the best of our knowledge, has only very recently been studied in simpler mediated settings (see, e.g., A Tight Regret Analysis of Non-Parametric Repeated Contextual Brokerage, ICML 2025). We conjecture that, due to the contextual nature of this setting, different techniques would be needed to address this extension. We will add a brief discussion of this extension to the revised version, as well as the clarifications above, so that the concrete motivations behind the independence assumption become clearer for future readers.

UCB and confidence levels. We confirm that the product of the UCBs the reviewer mentions does constitute a UCB for our objective, but the confidence level of the product differs from those of the factors. In our work, we choose specific confidence levels for the factors $\zeta_{K,\delta}$ and $\xi_{T,K,\delta}(n)$ defined at the bottom of page 5 so that an appropriately carried out derivation leads to the desired bounds. The full derivation can be found in the appendix (it ends at the bottom of page 26).

Necessity of pure exploration. Great question! We conjecture that some amount of "pure exploration" is indeed necessary, and that the amount allocated by our algorithm is likely the correct order of magnitude. The intuition is that our objective function (the expected gain from trade) can be decomposed as a sum of products of terms, some of which are not directly observable (see Step 2 of the proof sketch on pages 6-7). To estimate these hidden terms (which can be thought of as integrals over prices in $[0,1]$), one has to post prices that are spread over the entire unit interval. This is true even if one were given two distinct prices (one of which is optimal) and asked solely to determine which of the two was the optimal one. Still, the reviewer might wonder if perhaps the decomposition we provide is not the "best" that can be proven, and if the objective can be written in a different way that includes no hidden integral terms. Again, we believe this is not possible because of a "revealing action" phenomenon that was observed in the seminal work of Cesa-Bianchi et al. (A Regret Analysis of Bilateral Trade, EC 2021), which studies a special case of our setting. There (see Figure 2 in the arxiv version of the paper), the authors show that the learner can be forced to post prices that are known to be suboptimal and far from potentially optimal prices in order to gather usable information about these potentially optimal prices. This essentially amounts to forcing the learner to spend $\Theta(T^{2/3})$ rounds of "pure exploration". We are happy to add this discussion to the revised version as well.

We hope our answers helped clarify all lingering doubts.

If this is the case, we'd kindly ask the reviewer if they would consider readjusting their score.

Can you discuss your assumptions further? Yes, we would be happy to provide a deeper explanation.

In a real-world sense, Assumption 1.1 (i.i.d. supplier costs and retailer utility functions) implies that the behaviors of suppliers/retailers follow the same general pattern over time without being influenced by past interactions. In well-known platforms, where the number of users is high, the platform rarely sees the same supplier/retailer within a short window and the population of suppliers/retailers tends to be stable over time. This makes the i.i.d. assumption a reasonable approximation. For example, Airbnb, one of our motivating applications, has over 5 million hosts (i.e., suppliers) as of March 2025. On the other hand, small-scale platforms may violate the assumption as the same participants may return frequently, and the population may shift over time. Therefore, if the focus is on established platforms, the i.i.d. model is appropriate.

For Assumption 1.2 (independence between the supplier's cost and retailer's utility function), we refer the reviewer to our response to Question 1 of reviewer LSey (labeled by: Can we assume suppliers' costs are independent of retailers' utilities?) for a detailed explanation.

Regarding Assumption 1.3 (Lipschitz supplier cost cdf), this condition ensures that the cost of supplying a good varies gradually across suppliers, rather than abruptly. In other words, there are no large clusters of suppliers with costs concentrated in a narrow price range. This is a natural assumption guaranteeing that small changes in the trading price lead to stable changes in the likelihood of the trade. As a counterexample, suppose that a large proportion of rideshare drivers in a population refuel at the same gas station in a region where fuel prices are relatively stable. In this case, many drivers have nearly identical costs, resulting in a sharp spike in the cdf of supplier costs around the shared fuel price, which is a violation of our assumption. As a result, a small change in the trading price could cause a large proportion of drivers to accept a trade, causing unstable or unpredictable outcomes. We would argue that these types of scenarios with highly concentrated distributions are not overly common in practice. Thus, the assumption of Lipschitzness is well-justified in most real-world scenarios.

Assumption 1.4 (the expectation of the retailer’s optimal utility at price 1 is 0) means that, on average, retailers gain nothing if the trading price is set to its maximum value. Intuitively, the highest possible price is too high to justify any purchase by a retailer, resulting in zero net gain. For example, a rideshare rider may open the Uber app to check if the fare is below their personal threshold that they are willing to pay. If the price is at its highest possible value, it will exceed their threshold, making it likely the user will either walk or switch to a different service, such as Lyft. This behavior corresponds to a capped utility function, which is a common family of retailer utility functions where utility is zero beyond a certain price. One practical scenario in which this assumption is violated is when demand is inelastic: for instance, if a retailer must buy a certain quantity of the good no matter the cost. Following our previous example, the rider may be willing to purchase a ride at the maximum price if no alternative transportation options exist, e.g. if Uber is the only available service. That being said, such cases typically require a pure monopoly over a market or an emergency setting, which are relatively rare.

In an i.i.d. setting, the incentive-compatibility proved in Theorem 2.1 is not that surprising. We will clarify what follows in the revised version. Note that, even in an i.i.d. setting, participants may have an incentive to misreport their evaluations. Consider, for example, first-price auctions. Even if a bidder (identified by their valuation) is drawn i.i.d. from a family of bidders and will never return after a single interaction, they still have an incentive to shade their bids (i.e., to under-report their evaluations), because that is the only way they can gain a positive utility in a first-price auction mechanism. This is due to how the mechanism operates more than how the valuations of the participants are generated.

Add error bar and statistical significance. Thank you for the suggestion. We have updated the code for generating the plots to include error bars for the regret (95% confidence intervals calculated using the normal approximation). We would be happy to include these updated plots in the revised version.

Unfortunately, we are not allowed to post any images here. However, to provide some context for the updates, the following table shows the algorithm's average regret and 95% confidence intervals at every 100,000 iterations, where the algorithm was run for 700,000 iterations across 100 repeated trials (with a uniform supplier cost distribution and linear-capped retailer utility):

To give a visual, we note that although the error bands vary slightly across different supplier cost distributions and retailer utility functions, their thickness in both directions generally matches or is less than that of the regret curves (when run with 100 repeated trials). In other words, when the error bands are included, each regret curve visually appears, at most, about three times thicker.

Add info about your computing environment and execution times. We would be happy to include these details in the revised version. For reference, we ran our experiments on a 14-inch MacBook Pro with an M1 Pro chip ($10$-core CPU, 16-core GPU) and 16 GB of RAM. With this configuration, each plot takes at most around 12 minutes to generate when running each experiment for 100 repeated trials using the updated code.

How might changing the mediator's objective function affect the learnability, regret bounds, or even the mechanism design properties? Great question! The short answer is that those properties will vary depending on the objective. Consider the following three examples to illustrate some possible variations.

1. If the learner earns a commission $\alpha \in [0,1]$ (thought of as a percentage) and tries to maximize their return, their objective function becomes $p\mapsto\alpha p U^{\sharp}_t(p) \mathbb{I}$ { $C_t \le p$ }.

2. If the learner posts two different prices $(p,q)\in [0,1]^2$ with $p \le q$ to the supplier/retailer and tries to maximize their margin, their objective function becomes $(p,q) \mapsto (q-p) U^{\sharp}_t(p) \mathbb I$ { $C_t \le p$ }.

3. If the learner tries to maximize a fair notion of gain from trade, their objective function, inspired by Bachoc et al. [2024], could become $p \mapsto \min$ { $U^*_t(p), p- C_t$ } $\cdot \mathbb I$ { $C_t \le p$ }.

Regarding learnability/regret bounds:

• In the first two examples, the learner has access to bandit feedback. Hence, under suitable assumptions that guarantee the (at least one-sided-)Lipschitzness of the objective function, one could obtain regret rates of order $T^{2/3}$ in the first case (because the space is $1$-dimensional) and $T^{3/4}$ in the second case (because the pair of prices $(p,q)$ such that $p \le q$ form a $2$-dimensional manifold).

• For the third example, the learner cannot observe their own reward (the received feedback $\mathbb{I}$ { $C\le p$ } and $U^{\sharp}(p)$ is not enough to directly reconstruct $(C-p)$ or $U^{*}(p)$, and hence the learner does not have bandit feedback). Therefore, the problem becomes more challenging and some additional tricks would be needed to be able to reconstruct enough of the expected reward to guarantee learnability.

Regarding the mechanism-design properties:

• In the first and third examples, the utilities of both the supplier and the retailer stay the same, so Theorem 2.1 should extend naturally.

• In the second example, a proof like the one in Theorem 2.1 shows that incentive-compatibility and individual rationality are preserved. However, the mechanism can only be guaranteed to be weakly budget balanced (meaning that the learner does not subsidize trades but is allowed to siphon value from them).

We are happy to add these future directions to Section 7 in the revised version of this work.

We hope our answers helped clarify all lingering doubts.

If this is the case, we'd kindly ask the reviewer if they would consider readjusting their score.

We thank the reviewer for their thoughtful engagement. If any remaining concerns stand in the way of a more positive assessment, we would be grateful for the opportunity to address them.