Online Learning in the Repeated Mediated Newsvendor Problem
Authors: Nataša Bolić
Tommaso Cesari
Roberto Colomboni
Christian Paravalos
Venue: NeurIPS 2025 poster ()
Keywords: Theory
theoretical analysis
regret guarantees
bandits
online learning
newsvendor problem
Primary area: theory
TL;DR: We investigate a mediated version of the newsvendor problem from an online learning perspective

Abstract: Motivated by real-life supply chain management, we study a repeated newsvendor problem in which the learner is a mediator that facilitates trades between suppliers and retailers in a sequence of supplier/retailer interactions. At each time step, a new supplier and retailer join the mediator's platform with a private production cost and utility function, respectively, and the platform proposes a unitary trading price. The supplier accepts the proposed price if it meets or exceeds their unitary production cost and communicates their decision to the platform; simultaneously, the retailer decides the quantity to purchase at the proposed trading price based on their private utility function and sends their decision to the platform. If the supplier accepts the trading price, the transaction proceeds, and the retailer purchases their chosen quantity of units, paying the product of this quantity and the trading price to the supplier. The mediator's objective is to maximize social welfare. We design an online mediator's pricing strategy that features sharp regret rates under some natural assumptions, and we investigate the necessity of these assumptions, proving that relaxing any of them leads to unlearnability.

Online Learning in the Repeated Mediated Newsvendor Problem
Nataša Bolić'
Tommaso Cesari'
Roberto Colomboni
Christian Paravalos'
EECS, University of Ottawa, Ottawa, Canada DEIB, Politecnico di Milano, Milano, Italy
3 DDpartment of CS, Università degli Studi di Milano, Milano, Italy
(nboli039, tcesari, cpara006)
euottawa. (aotra00ee@uutttaaaaaaa roberto. colomboni wwtpoomiippommimm.mm.m iil
Abstract
Motivated by real-life supply chain management, study repeated newsvendor problem which the learner mediator that facilitates trades between suppliers and retailers in sequence of supplier/retailer interactions. At each time step, a new supplier and retailer join the mediator's platform with a private production cost and utility function, respectively, and the platform proposes unitary trading price. The supplier accepts the proposed price meets or exceeds their unitary production cost and communicates their decision to the platform; simultancously, the retailer decides the quantity to purchase at the proposed trading price based on their private utility function and sends their decision to the platform. If the supplier accepts the trading price, the transaction proceeds, and the retailer purchases their chosen quantity of units, paying the product of this quantity and the trading price to the supplier. The mediator's objective is to maximize social welfare. We design online mediator's pricing strategy that features sharp regret rates under some natural assumptions, and we investigate the necessity of these assumptions, proving that relaxing any of them leads unlearnability.
Introduction
The newsvendor problem is central topic in the analysis of supply chains. In its classical one-shot version AArow et al. [951]. I, the supplier chooses and reveals trading price. After observing the trading price, the retailer orders a certain quantity of the good, deciding how much order based on a privately held utility function that depends on their needs and wants. The repeated version studied Huang and Sošić (2010) and Cesa-Bianchi al. 2023a generalizes this problem to a sequence of supplier/retailer interactions.
1.1 Motivations
To the best of our knowledge, the newsvendor problem has only been studied under the assumption that the supplier determines the trading price. This assumption falls short in many real-life applications where an independent, third-party mediator, whose goal is serve the interests of both parties, selects the trading prices. The following examples illustrate markets where mediator- naturally arise and prove to be beneficial. Digital advertising intermediaries (c.g.. ad-exchange platforms) propose clearing prices for ad impressions or clicks to publishers, and ad advertisers decide how many to purchase. Cloud computing platforms (e.g.. AWS, Azure, GCP) propose may-as-you-ge rates to data centers or resource providers, and users needing computing power decide how much of it to use. Real estate rental intermediaries (e.g., Airbub for short-term accommodations or corporate housing for long-term stays) propose nightly, weekly, monthly rates to property owners, and renters decide the duration their stay. Online freelance marketplaces (e.g., Upwork, Fiverr) propose hourly
pricing could
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

or per-task rates to freelancers (e.g., designers, programmers), and users decide how many hours or tasks to book. Ridesharing platforms (e.g,, Uber. Lyft) select the per-mile prices of rides, drivers decide to accept or reject the prices posted by the platform based on the cost of fuel/car maintenance, and riders choose the distance of the ride. Lastly, microgrid energy operators propose real-time prices to households capable of generating energy, and other households or businesses choose how much energy to purchase.
In addition to practical motivations, this problem is also intriguing from a theoretical point of view. Indeed, the repeated newsvendor problem is strict generalization of the popular dynamic pricing problem. Consequently, our proposed repeated mediated newsvendor problem strictly generalizes bilateral trade (see Appendix [ a formal proof of this claim), a setting that has recently garnered significant interest within the machine learning community [Cesa-Biaage Bianchi et al.) 2021
c 2024 Bernasconi et al., 2024 [Bolć et al., 2024 [Bachoe et al. 2024 Gaucher et al.,
Azar et al. 2022 2024
2025 Hajiaghayi et al.
2025 Deng et al. 2025]. Notably, our tight regret guarantees also recover
optimal regret rates (up logarithmic terms) the important special case of bilateral trade.
All of these considerations give compelling practical and theoretical reasons to study this problem and characterize its learnability.
1.2 Formal setting
Let USC be the set of all [0, 1]-valued upper semi-continuous functions defined on [0, 1]. Select, for any u E USC and price p E [0, 1], u (p) E argmax ("(g) - p q) (our theory holds irrespectively of how this selection is made, i.c., of how ties are broken) and define u (p) = u(u* (p)) p- (()). Up to simple rescaling, we can and do assume without loss of generality that trading prices, suppliers' costs, and quantities exchanged belong [0, 1]. We also assume that retailers' utilitics belong to USC, minimal condition needed for u* to be well-defined! |
The online learning protocol for the repeated mediated newsvendor problem (RMNP) we study proceeds as follows.
Online learning protocol
1:
for each time 2,..... do
2: A supplier with a private C₁ and a retailer with a private (gross) utility U2 join the
mediator
3: The mediator proposes a trading price P.
4: The supplier communicates I[C, Pt] (i.e., whether they accept the trade, which happens if and only if the proposed trading price Pt is no lower than their production cost Ct), and the retailer communicates U.*t (P:) (i.e., the quantity they are willing to buy at price Pt, which is the quantity that maximizes their net utility when the trading price is Pt) the mediator.
5: if C. < Pt then the retailer buys the quantity # (Pt) from the supplier at a total price of Pt- (P+))
The mediator's reward at every round t is the so-called gain from trade, defined as the sum of the net gains of the supplier and retailer More precisely, when the supplier's cost c E [o. 1] and the buyer's utility function is USC, the gain from trade at trading price p E [0, 1] is defined as
g(p, G, u) = (p-
T SP
supplier's net gain
retuiler's net gain
trade accurs
'This is strictly weaker condition than the commonly assumed Lipschitzness that is still sufficient for theory.
'The reader might wonder why the mediator doesn't ask the two parties for their private cost and utility before proposing trading price. The reasons for this choice have deep roots in mechanism design dating back the wiining work of Myerson and Satterthwaite [1983]. We will address them in Section 2
"Note that, from regret- minimizationn perspective, this is equivalent to setting the social welfare as the mediator's objective.

---

The goal of the mediator is to minimize the regret defined, for any time horizon T E N, by
I Eo(P.
RT
E pEfo,1]
sup
E gl. Cr U.)
We develop our theory under four key assumptions (and will analyze the necessity of each of them).
Assumption 1.1. The model is stochastic: the sequence (C,U), (CI, U.) (C2, U2).... of supplier's costs and retailer's utility functions is i.i.d.
Assumption 1.2. The supplier's 's cost independent of the retailer's utility function U.
Assumption 1.3. The cumulative distribution function (cdf) of the supplier's cost C' is m-Lipschitz, for some constant m.
Assumption 1.4. EE [1)] = 0; i... the expectation of the retailer's optimal utility at price 1 is O.
In real-world sense, Assumption 1.1 implies that the behaviors of suppliers/retailes follow the same general pattern over time without being influenced by past interactions. In well-know platforms, where the number of users is high, the platform rarely sees the same supplier/retailer within short window, and the population of suppliers/retailers tends to stable over time. This makes the i.i.d. assumption reasonable.
Assumption 1.2 simply means that the supplier's production cost does not directly influence the retailer's ss utility function. A first reason why this 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 are often distinct from one another. For example, fall in steel prices lowers bicycle-frame costs but does not necessarily change commuter's willingness to pay for the bike. Another reason that in many mediated markets, the item traded is fixed (e.g.. specific SKU, ride, or room-night). In this case, switching supplier for another affects the production cost but not the retailer's 's valuation of that identical item. In other words, if it is always the same type of item that is being traded, it is realistic random draw of the supplier would not influence that of the retailer. Hence, this assumption models the real-life fact that the utility earned by the retailer is only directly affected by the trading price.
assume that the
Assumption 1.3 is common, mild technical assumption that prevents highly concentrated distribu- tions capable of generating pathological and unrealistic scenarios. In other words, it prevents large clusters of suppliers with costs concentrated in a narrow price range, which guarantees that small changes in the trading price lead to stable changes in the likelihood of the trade. As 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 result, a small change in the trading price could cause 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 wusl-justified in many real-world scenarios.
Finally, Assumption 1.4 naturally states that if good reaches the highest possible price of 1, then the retailer has no opportunity for profit and thus will not purchase any amount, resulting zero utility. For example, rideshare rider may open the Uber app to check whether the fare is below their personal threshold that they are willing to pay. At the maximum fare, it will exceed their threshold, making it likely the user will either walk switch to different service, such Lyft. This behavior corresponds to a capped utility function, where utility vanishes beyond a certain price. One scenario in which this assumption is violated is when demand is inelastic: for instance, if retailer must buy certain quantity of the good no matter the cost. Following our previous example, the rider may be willing purchase 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 pure monopoly over market or emergency setting, which relatively uncommon.
Hence, Assumptions 1.I are mell-motivated by waal-wrldd factors. We further investigate each assumption in Theorem 5.1 showing that they are not only justified but necessary for learnability.
3

---

1.3 Overview of our results
Our contributions are fourfold.
1. We prove that the mediated newsvendor mechanism is incentive compatible, individually rational, and budget balanced (Theorem 2.1..
2. We present an algorithm (Algorithm 1 for the repeated mediated newsvendor problem and prove
that, under Assumptions 1.1 1.4 the algorithm achieves (TT2/3) regret (Theorem 3.3
We prove the optimality of Algorithm|| by establishing matching lower bound of order (2(2233).
showing that its rate is unimprovable, up to logarithmic terms (Theorem 4.1).
4. We investigate the necessity of Assumptions
proving that lifting any one of them makes the problem unlearnable, even if the remaining three hold (Theorem 5.1
1.4 Techniques and challenges
In this section, we outline the main challenges arising from the analysis of our setting, as well as the techniques we employed to overcome them.
Uncountable action space. First, the action space is uncountably infinite, a hurdle that usually prevents online learning techniques from working without further assumptions. One typical condition that enables online learning algorithms to work in such action spaces is that the expected reward function is Lipschitz, which opens the door to using discretization methods. However, our setting, the expected reward function is not even one-sided Lipschitz (a weaker regularity condition that is still typically sufficient to guarantee learnability) without further assumptions. We overcome this obstacle by showing that, under the mild condition that the distribution of the supplier's s cost is not too concentrated, we can in fact ensure that the expected reward function is one-sided Lipschitz, thereby unlocking discretization methods. Importantly, the validity of this mild assumption is not a limitation of our analysis, as we show that the problem becomes unlearnable when the edf of the supplier's 's cost is not Lipschitz (Theorem 5.1
Severely limited feedback. Even under the assumption that the edf of the supplier's cost is I Lipschitz, significant challenges remain. In particular, the mediator cannot implement standard bandit despit the rich body of literature on this topic-because the available feedback is too limited to reconstruct standard bandit feedback. Indeed, whenever trade occurs, the reward function equals the sum of the supplier's net gain (P; -P--C, C.) (P,) and the retailer's 's net gain U, (Pt). However, the mediator only learns a threshold about the supplier's 's cost ".-specifically, that is below the posted price P.. Moreover, instead of observing the retailer's net gain U, (P:), the mediator only receives the quantity 0.*h (Pt) that the retailer wishes purchase at price Pt. Consequently, one must find a way to reconstruct the supplier's 's net utility from the threshold feedback and the retailer's net utility from the quantity purchased.
first hint on how this feedback can be used comes from Step I of the proof sketch of Theorem 3.3
which indicates that when the supplier's 's cost is independent of the retailer's utility function, the expected reward function at any price E [o, 1] is equal to E [U # (p) E (p C)+ + E [[[C < p} (p)) Thus, if one could reliably estimate the terms E (p- C)+ and E [p)]. then the feedback available to the mediator after each interaction would fact allow them to estimate the (expected) reward, turning the original problem into, essentially, a bandit problem. Under the assumption that the suppliers' costs and retailers' utilities form an i.i.d. process, we design a strategy where, first, we run an initial phase to construct optimistic estimates of the terms [ - C]+] and E [p)) and then subsequently run UCB-type bandit algorithm with the available feedback.
The last missing and crucial ingredient is to determine how to run the first phase build these optimistic estimates for the terms that we do not have direct access to. To do this, we leverage the celebrated Envelope Theorem of Milgrom and Segal (see Appendix F and show that, via an integration procedure, we can approximately and optimistically reconstruct the net utilities [((p - -]-] and E. (p)] at any price p. This reconstruction uses the mediator's feedback by querying prices at points arranged on uniform grid, which may be located far from p.

---

We conclude this section by remarking that the assumptions that led us to this strategy are not merely limitations of our analysis. Indeed, as shown in Theorem [5.]] carefully constructed impossibility results imply that relaxing any of them leads to unlearnability.
1.5 Related work
The newsvendor problem first appeared in Edgeworth [888] and was later formalized by Arrow et al. [951]-we we refer the reader to Coooii 2012 for a survey of the many variants of Arrow's model.
A theoreicc formulation of the newsvendor problem with competing retailers was proposed by Parlar [1988] -see also Lippman and McCardle [1997]. Mahajan and van Ryzin (2001) J. Netessine
et al. 2006]. Waan and Gerchak [2003] use a Stackelberg game to model a situation where an assembler has to buy components from different suppliers. Lariviere and Porteus (00T) study a
model where supplier and retailer interact through a price-only contract, and compare its efficiency with the efficiency of an integrated system. [Adida and DeMiguel [201 I] consider a competitive inventory model with several suppliers and several retailers, and prove equilibrium uniqueness under some symmetry conditions. We refer the reader to Cachon and Netessine (2006) for a survey of the literature on game-theoretic models in supply chain analysis and to SSilbermayr 2020] for a more recent and specific survey on newsvendor games.
The mediated newsvendor problem is strict generalization of the bilateral trade problem. The litera- ture on bilateral trade is extremely rich and has experienced steady growth since the fundamental work of Myerson and Satterthwaite [1983]. Classically, bilateral trade has been explored in the and approximation perspective
one-shot setting, mainly from a game-theoren
Gfolini-Baldssche 2016 2017 Blumrosen and Mizrahi 2016 Brustle et al.) 2017 Golini-Baldeschi et al. 2020
et al.
Babaioff et al. 2020 Dütting et al. 2021 Deng et al. 2022 Kang et al. 2022 Archbold et al. 2023). For fairly complete overview on this literature, see, e.g.. Cesa-Bianche et al. [2023c]. On the other
hand, a recent stream of literature has explored bilateral trade in repeated setting through the lens of online learning. Given its greater relevance to our work, we focus on this literature.
In Cesa-Bianchi et al. 2024]. Bacchhocchi et al. [025]] Gaucher et al. [0025]. Bachoc et al. [022]]
et al. [202]] Azar et al. [2022], (Cea--Bianchh et [2023c b). Bernasconi al.
2024 Bolié et al. (2024), Bachoc et al.] [2025a b). Cesari and Colomboni [2025]. J. the authors
examined the repeated bilateral trade problem where sellers and buyers trade din-divisible items. At each interaction with a new seller-buyer pair, the platform proposes a trading price, and the current item is traded if and only if the proposed price exceeds the seller's 's private valuation and is below the buyer's. When trade occurs, the buyer pays the posted price to the seller, the seller transfers the item to the buyer, and the platform is rewarded with the gain from trade, i.e., the sum of the seller's 's and buyer's utility. In [esa- et al. [202T 2023c], the authors investigated and obtained sharp regret bounds when sellers' and buyers' valuations for the non-divisible items being traded represented by two random sequences of numbers (S.) (B:)teN-form form two i.i.d. sequences, while also showing that the adversarial case is unlcarnable in general. Azar et al. [2022] managed to obtain Icarnability in the adversarial case by relaxing the notion of regret to that of 2-regret. When the platform can post two different prices to sellers and buyers, but is still not allowed to subsidize trades, -isachiincchi eet al. 20036 2024) achieved learnability using the usual notion of regret when the adversary belongs the class of smoothed adversaries. [Bernasconi al. (2024) managed achieve learnability in the adversarial case by allowing the platform to subsidize trade, as long as the subsidization comes from revenue obtained from previous seller and buyer interactions, Chenn al. 2025 improved on these results, and Lunghi et al. [2026] explored trade offs between budget violations and attainable regrets regimes. Bacchiocchi et al. [2025] investigated an asynchronous protocol for bilateral trade when sellers are queried only when a buyer is already secured. Gaucher et al. (2025) studied contextual version of bilateral trade problem. Bachoc et al. [2024] proposed a variant of the gain from trade as reward to promote fair division of profits among sellers and buyers. [abaioff et al. [2024). Lunghi et al. [2025] explored bilateral trade with multiple buyers. [Bolić et [2024] investigated and characterized learnability in the i.i.d. setting when, at each time step, the two traders do not have predetermined seller and buyer roles, but can switch from one to the other depending on the proposed
trading price. This last setting has been further investigated with contextual information in Bachoc
et al. [2025a]b b) and with the different objective of maximizing volume instead of gain from trade in Cesari and Colomboni 2025).
5

---

Finally, divisible items have also been recently proposed and studied in a different welfare maximiza- tion setting for dynamic pricing in Cesa- Desa-Bianchi al. (2025].
2 Incentive compatibility, individual rationality, and budget balance
In this section, we show that the mediated newsvendor mechanism is incentive compatible, individu- ally rational, and budget balanced- that is, the supplier and retailer gain nothing by misrepresenting their cost or utility function to the mediator, they never lose money by participating in a trade, and the mediator cannot subsidize or siphon welfare from trades (
Incentive compatibility, We say that the mediated newsvendor mechanism is incentive compatible if, letting be the supplier's cost, u the retailer's utility, and p the proposed trading price, it is dominant strategy for the supplier to accept a trade at price if and only if c S and it is a dominant strategy for the retailer select the quantity # (p).
Individual rationality. We say that the mediated newsvendor mechanism is individually rational if the net utilities of the supplier and the retailer are non negative. Here, given a production cost c, an order quantity q, and trading price p, the net utility of the supplier is defined (gp - qc)llfc p}. and the net utility of the retailer is defined as u(q)= pg.
Budget balance. We say that the mediated newsvendor mechanism budget balanced if, whenever I, and the sum x is transferred in its entirety the supplier.
a payment of needs to be transferred from the retailer to the supplier, the retailer is asked for exactly
Theorem 2.1. The mediated newsvendor mechanism is incentive compatible, individually rational, and budget balanced.
Proof sketch (full proof in Appendix By. We separately prove the three claims in the statement of Theorem 2.1 To show incentive compatibility, we prove that any attempt by either the retailer or the supplier to misreport their private information- whether by over- under-reporting le-le to decrease in their respective utilities. Next, individual rationality follows directly from the fact that suppliers will never accept trade when their costs exceed the offered price, and that retailers assumed to optimize their net utility, ensuring it is always non-negative (since they always have the option abstain from purchasing, resulting in a utility of O). Finally, the audget-balancee property can be derived from its definition within the context of this setting.
We remark that incentive compatibility, individual rationality, and budget balance are three of the four classic desiderata in bilateral trade mechanisms like the newsvendor problem. The fourth one is market efficiency, that is, the ability to make the supplier and retailer trade every time they have the opportunity to do so-i... whenever there exists a p such that c S p and # (p) > O. The Nobel-winning work on bilateral trade of Myerson and Satterthwate [188]] shows that, in general, the above four properties cannot hold simultaneously. Therefore, Theorem 2. yields a maximal set of properties that any bilateral trade mechanism can satisfy and is thus unimprovable.
A no-regret algorithm for RMNP
In this section, we present our Algorithm I and provide an upper bound on its regret.
To lighten the notation, we begin by introducing the following confidence radii that we repeatedly use. For each K E N, 8 E (0, 1), and T, n. N, we define
1 + (2ln(8K/8) CK.6
(r, 2 2ln(8KT/8)
and
K
n
*Note that result does not follow directly from Assumption I.1 since even in an i...d setting, participants can benefit from misreporting their valuations. E.g.. in first-price auctions, bidders have an incentive to under- report despite i..d. draws and one-shot participation. Thus, it is essential to analyze the mechanism, not just the generation of valuations, to assess incentive compatibility, individual rationality, and budget balance.

---

We are now ready to present our algorithm. Algorithm 1 takee the time horizon T, discretization
parameter K E I and confidence parameter ó E (0, 1) as input. Then, it builds grid of (K + 1)- equispaced points 0 = po <. P1 <.. < PK 1 and spends the first K22 rounds by posting the K' prices Po: Pl. ... PK-1 in a round-robin fashion. Afterwards, for any j (0, 1,..., K 1]. uses this information to build upper confidence bounds Fj + SK,5 (resp. Gj + (K,s) ) for (p)) (resp. E [((;; c)+]). These two terms will be useful to build estimates of the two multiplicative terms will
reconstruct the expected reward p ~ E. [g(p, C,U)] when evaluated at the points PK PK- After those K rounds, the algorithm follows upper confidence bound strategy on the reward function, leveraging the previous estimates, and the bandit feedback it collects along the way.
Po, pl.......... ................................
Algorithm
input: Time horizon T' E N, discretization parameter K E N, and confidence parameter à E (0, 1)
init: Set Vj E {O..... }, Pj = k A, = (0) = N₁ (0) =
for each time
1.2.... do
2: if < K2 then select I == 1 --1 (mod K)
3:
if K2 then
(N, +(r.x(N,((tt1)) (G, (K,6)
4:
Update Vi {O..... K- 1}.90-1(1) =
Nt(1-1)
(,
+
N2(1-1) + + (Nx(1-1)))) (F) (K,8)
where, Vj E F] K-1 A. (K*)
and Vjj EK KK- G, = =E
B, (M.)
K
5: Select 4 argmax,e (0..,KX-0-.....
6: Post price P: PI, and receive feedback 11[C, < Pi] and U (Pi)
7: Update Vj E (O..... ......K K - 11. (t) = N2 - 1) [ij = le).
Ar, (Nr, (t) = A,, (N, (t- +U (P.), B1, (t), = B₁, (N P.)
To provide regret guarantees for Algorithm 1 the retailer's optimal net gain u" (that appears in the gain for trade) with the retailer's desired quantity function a# (that appears in the feedback the learner receives), for any (gross) utility function u E USC.
we begin by proving lemma that allows us to relate
Lemma 3.1. Ifu e USC, then.for for any selection of t and any S p1 < p2 S 1, holds that
u" (pt) - n² (p((p))))))))))))(())) = S p2 a* (A)dA
The key idea of the proof is leveraging Milgrom and Segal's Envelope Theorem, which establishes an integral representation of some transformation of func- tion in terms of another transformation of the same function. A careful derivation applied to the transformations w* and u# of leads to the result.
Proof sketch (full proof in Appendix C.
Before stating and proving our regret upper bound for Algorithm | (Theorem 3.3). we require a second technical lemma, whose economic interpretation is that the retailer's net gain decreases the price increases, and so does the quantity that the retailer decides to buy.
Lemma 3.2. For any u E USC, the functions u² and t are monotonically non non-incrennee aen--ncreeainn.
Proof sketch (full proof in Appendix C. The monotonicity of u² a direct consequence of the pre- vious Lemma! 3.1 The same property can be proven for a through derivation involving lower bounding, for any 0 < P1 S P2 S 1, on the product (p2 - pp) (p1) - n (pz)). by exploiting some elementary properties of u² and #
Theorem 3.3. Assume that Assumptions I.I 1.44hold hold. we run Algorithm Baaaammmwwer with time horizon T, discretization parameter K = /3 and confidence parameter å = 3. then
1.4
Rr = 0TT2/3)
7

---

Proof sketch (full proof in Appendix C). The proof rests on four key ideas: 1. Although the learner does not observe the realized reward gained when posting a price, the expected reward associated with that price can be expressed indirectly, An initial phase can be used estimate the terms that cannot be directly observed, The discretization error can be carefully controlled, and 4. The regret suffered during the second (and main) phase can be managed by leveraging the feedback relative to the terms that can be directly observed.
a function of terms that can be estimated either directly or
Step I. Understanding the expected reward. The keystone of this analysis rewriting the expected
reward at a price E _ (p) E (p - C)+ + [|[[C' S p}] E (p)) Recall that the feedback
received by posting a price p at time t U (p) and I[C, S p). Thus, the two terms E [ (p)] and [[[[C S pp]] can be directly estimated using the observed feedback, whereas the terms E (pp ((pp-C) C)+]
and E [p) cannot.
Step 2. Estimating the "hidden" terms. Algorithm| 1 spends the first K2 rounds cycling over the K grid points Pn.... Px-1 -1 and gathering feedback samples. These samples can be used in non-trivial way to build high-proud probabbbbbbility optimistic estimates of TE [p - C)+] and E [p)] for every grid point p.
Step 3. Controlling the discretization error. The discretization error can be controlled by combining 3.1 and 3.2 with the Lipschitzness assumption on the supplier's cdf, obtaining, for and any p [pj.Pj+i]. that [s()) [(;;) = (
our two Lemmas
any E (0.
Step 4. Estimating the "observable" terms. In the second (and main) phase, Algorithm exploits the optimistic estimates of the "hidden" terms built in the initial phase, putting them together with natural UCB estimates of the "observable" terms that are built sequentially. This combination provides high-probabillity guarantees for the estimator -t-1 maintained on Line the algorithm, uniformly across all points in the grid. More precisely, with probability at least 1 - 5, it holds that, for all
j E (0. K), (P;) S أr-(()) S f(p)) + 16 /2 (*KT) min / NN K).
Putting everything together. Combining the four steps above, one prove that the regret can be upper bounded as follows
KT T
T (
Rr = 0 T8 K22+
K log
KT
which, plugging in the values of K [T|/3] /31 and ò = t. yields the desired result.
Optimality of Algorithm
In this section, show that, up logarithmic terms, the performance of Algorithm I cannot be improved.
Theorem 4.1. Assume that Assumptions I.1 1.4 hold. Then, the worst-case regret of any algorithm satisfies
RT = Q(T2/3).
Proof sketch (full proof in Appendix The key insight obtain this result that our setting is proper generalization of repeated bilateral trade (we prove this formally in Appendix A). setting where the retailer's 's decision is restricted quantities Q₂ {0, 1}, where Q₂ I[P, S BB) and B, is the retailer's 's private valuation for the good on sale. In particular, we show that repeated bilateral trade can be seen as particular instance of the RMNP when the retailer's utility function U, is linear function from [0, 1] to [0, 1] with slope B, Once this reduction has been established, we can leverage tools from bilateral trade to obtain the desired lower bound.
As we mentioned in the proof sketch of Theorem 4.1 the RMNP is proper generalization of the better-understood repeated bilateral trade problem. Consequently, our algorithm and upper bound in Section 3 apply to the bilateral trade problem too, yielding near-optimal guarantees in this more restrictive case as well. We remark that it typically not true that an algorithm with near-optimal guarantees in online learning problem is also near-optimal in all special cases of the general
8

---

problem because, in general, algorithms tailored to special cases can exploit this knowledge to obtain better performance. Theorems 3.3 and 4.1 show that, instead, our Algorithm automatically adapts to bilateral trade, retaining its near-optimality.
5 Necessity of assumptions
The reader may wonder whether Assumptions I.1 1.4 are necessary for learnability, In this section, present strong negative result showing that the learning problem becomes unlearnable if even one of these assumptions is violated, regardless of whether the other three still hold.
Theorem 5.1. Assume that at least one of Assumptions [.4 does not hold. Then, even if the remaining three hold, the worst-case regret of any algorithm satisfies
RT = (.T).
Proof sketch (full proof in Appendix E.. The four points proved separately. For each one, build a family of "hard" instances, each satisfying exactly three of the four Assumptions 1.1 We
then show that every algorithm suffers linear regret in least one instance of this family.
6 Experiments
In this section, we empirically validate our theoretical results by simulating a variety of supplier cost distributions and retailer utility functions. Our goal is to illustrate the practical effectiveness of our algorithm and the necessity of Assumptions
To validate our theoretical upper bound, evaluate the regret of Algorithm I across several supplier cost distributions designed to represent realistic mediated market conditions. Firstly, we use the neutral baseline for our experiments. Then, model markets where
Uniform(O.) 1) distribution low-cost suppliers are prevalent but occasional high-cost suppliers exist, we consider two right- skewed distributions: a Beta(o 2. 3 = 5) and a Log-Normall, with the latter assigning more probability to high-cost suppliers. Finally, to represent markets with two distinct tiers of suppliers, we include a bimodal mixture 0.75 Beta(2, 5) + 0.25 Beta 2). which creates majority group of low-cost suppliers and a smaller, higher-cost group.
-0.5, o = 1) truncated [o, 1].
We also consider two realistic and prevalent families of retailer utility functions. Firstly, model satiable demand through the capped- -ineer utility function Uq)((9) = minfag (ag, aq), where the retailer's utility grows at constant marginal rate E [0, 1] until the quantity purchased reaches the saturation threshold q E [0. 1], after which purchasing additional goods generates no further benefit. For our experiments,
draw from Beta(5, 2) distribution and q from Beta(2,2) distribution. In this scenario, retailers generally place high value on initial purchases until inventory reaches a moderate level, at which point acquiring more goods yields no extra value to the retailer.
Secondly, we model diminishing marginal returns using the exponential utility function Ux(g)= = (1 -1-e->4) /A, where À >> 0 determines the overall valuation level. this case, the marginal gain from purchasing additional goods decreases progressively as the quantity increases. For our experiments, we draw X from a Log-NormallO, 0.5) distribution, resulting in retailers whose initial marginal valuations are generally moderate and whose marginal benefits decline smoothly as the quantity purchased increases.
Note that all supplier and retailer distributions described above satisfy Assumptions
meaning
that we expect that Rt 0(32/3) by Theorem 3.3
As expected, Algorithm I behaves according the theoretical guarantees we established across all the combinations of supplier and retailer distributions described above (see Figure I While the regret remains similar across seller distributions for given utility. the capped- -ineed-linear utility appears to have a moderately lower growth rate in regret than the exponential utility.
We utilize the distributions defined in the proof of Theorem 5.1 in Appendix E to illustrate the linear lower bounds empirically. In the proof sections corresponding to Assumptions 1.2 and I.4
we relax
For reference, we ran our experiments on MacBook Pro with an MI Pro chip (10-core CPU, 16-core GPU) and 16 GB of RAM. With the given configuration, each plot takes most around 3 minutes generate.

---

Regret over Time for Different Saller Velualions with Cappec-Linee Liner Utility
Regret over Time for Differant Soller Velueiions with Expooeenie Utlllyy
Regret over Time when Litting
Assumpttonss 1.1-]
Unforr
Accumation 1.3
20000
Seta
Log Normal
20020
haphtommal
100020
Ltt Assumption
Lower Bound
Seta Nodure
140020
Lower Bound
Usper Bourdd
Thearom Upoer Bound
LR Accumption
15000
35030
Lower
10000
20020
500C0
50000
40000
20000
01
Bound 502003
202000
400200
500000
Iound
Figure 1: The z-axis represents the time horizon T' and the y-axis represents the regret Rr. Each curve shows the mean regret over 30 random trials, with the shaded bands around the curves repre- senting the 95% confidence intervals on the regret computed under the normality assumption. The left and center plots illustrate the algorithm's 's performance across various supplier cost distributions under capped-linear and exponential retailer utilities, respectively. They include the theoretical upper bound from Theorem 3.3 (scaled down for visualization). The right plot shows the algorithm's 's performance when each of the assumptions is removed, using the distributions from the proof of Theorem 5.1 in Appendix B along with their lower bounds.
both assumptions in turn and construct two environments such that any algorithm will suffer linear regret under at least one of them. We sample from the first environment in each pair to generate the empirical results. For Assumption [.] the proof constructs two families of adversarial environments, adapted from those in Assumption 1.2 and shows that each family's worst-case regret is at least as large as the regret in the corresponding Assumption 1.2 environment. Hence, we select an adversary from the first family to generate the empirical regret of Algorithm with respect to sequence of supplier costs and retailer utility functions that is not i.i.d. For Assumption 1.3] the proof defines an infinite family of environments with non-Lipschitz supplier cost cdfs, showing that every learning algorithm suffers linear regret under at least one. Thus, we select a fixed environment from this family and display its regret in Figure I As expected, in each of the four configurations where one of the Assumptions 1.141.4 is lifted, the regret of Algorithm T grows linearly (see Figure
7 Conclusions, limitations, and future directions
Our paper explores a repeated version of the mediated newsvendor problem. After proving that the mediated newsvendor mechanism is incentive compatible, individually rational, and budget balanced, we provide a comprehensive analysis of the repeated mediated newsvendor problem consisting of matching upper and lower regret bounds of order T2/3 under four key assumptions, along with impossibility results if any of the assumptions are removed.
Our research encourages further exploration of this setting. A minor limitation of work is that our regret guarantees in Theorem 333 are tight up to logarithmic factors, hence further research needed to determine the precise upper or lower bound. Additionally, one could investigate a fair variant of this setting in the spirit of [Bachoc et al. [2024). where the instantaneous objective of the learner is the minimum between the supplier's 's and retailer's s utilities rather than their sum, A further avenue could be to explore contextual setting where a context vector is available to the learner at each round, to capture shared shocks (e.g., seasonal effects) that influence both suppliers and retailers. Another interesting extension could be to examine a yeakly-budget balanced version of this setting where the learner can post two potentially distinct prices to the retailer and the supplier. A final intriguing line of research would be to consider bargaining mechanism for the supplier where, instead of simply accepting/rejecting the proposed trading price, they are allowed counter. We leave these interesting directions to future research.
10

---

Acknowledgments and Disclosure of Funding
NB. CP, and TC acknowledge the support of NSERC through USRA (Undergraduate Student Research Awards).
TC also gratefully acknowledges the support of the University of Ottawa through grant GR002837 (Start-Up Funds) and that of the Natural Sciences and Engineering Research Council of Canada (NSERC) through grants TEPIN-2023-0366 (Discovery Grants Program) and DGECR2023-00288 (Discovery Grants Program, DGECR Discovery Launch Supplement).
RC is partially supported by the MUR PRIN grant 2022FKNNS5K (Learning in Markets and Soci- ety), the FAIR (Future Artificial Intelligence Research) project, funded by the NextGenerationnFU program within the PNRR-PE-AI scheme, the EU Horizon 144-2022-HUUMAN research and innovation action under grant agreement 101 120237, project ELIAS (European Lighthouse Al for Sustainability).
References
Kenneth J. Arrow, Theodore Harris, and Jacob Marschak. Optimal inventory policy. Econometrica, 19:250-272, 1951. ISSN 0012-9682.
Xiao Huang and Greys Sošié. Repeated newsvendor game with transshipments under dual allocations. European Journal of Operational Research, 204(2):274-284, 2010.
Nicolò Cesa- Besa-Bianchi, Tommaso Cesari, Takayuki Osogami, Marco Scarsini, and Segev Wasserkrug. Learning the Stackelberg equilibrium in newsvendor game. In Proceedings the 2023 Interna- tional Conference on Autonomous Agents and Multiagent Systems, pages 242-250, 2023a.
Nicolò
Tommaso Cesari, Roberto Colomboni, Federico Fusco, and Stefano Leonardi. A regret analysis of bilateral trade. In Proceedings of the 22nd ACM Conference Economics and Computation, pages 289-309, USA, 2021. Association for Computing Machinery.
Nicolò Cesa- Bianchi, Tommaso Cesari, Roherto Colomboni, Federico Fusco, and Stefano Leonardi. Repeated bilateral trade against smoothed adversary. In The Thirty Sixth Annual Conference on Learning Theory, pages 1095-1130, USA, 2023b. PMLR, PMLR.
Nicolò Cesa-Biancd Tommaso Cesari, Roberto Colomboni, Federico Fusco, and Stefano Leonardi. Bilateral trade: A regret minimization perspective. Mathematics Operations Research, 2023c.
Nicolò Cesa-Bianche Tommaso Cesari, Roberto Colomboni, Federico Fusco, and Stefano Leonardi. Regret analysis of bilateral trade with a smoothed adversary. Journal of Machine Learning Research, 25(234):1-36. 2024.
Yossi Azar, Amos Fiat, and Federico Fusco. An alpha-regret analysis of adversarial bilateral trade. Advances in Neural Information Processing Systems, 35:1685-1697 2022.
Yossi Azar, Amos Fiat, and Federico Fusco. An a-regret analysis of adversarial bilateral trade. Artificial Intelligence, 337:104231, 2024.
Martino Bernasconi, Matteo Castiglioni, Andrea Celli, and Federico Fusco. No-regret learning in bilateral trade via global budget balance. Proceedings of the 56th Annual ACM Symposium on Theory of Computing, 2024.
Natasa Bolić, Tommaso Cesari, and Roberto Colomboni. An online learning theory of brokerage. In Proceedings of the 23rd International Conference on Autonomous Agents and Multiagent Systems, pages 216-224, 2024.
François Bachoc, Nicold Cesa-Bianchi, Tommaso Cesari, and Roberto Colomboni. Fair online bilateral trade. In The Thirty-eighth Annual Conference on Neural Information Processing Systems, 2024.
Solenne Gaucher, Martino Bernasconi, Matteo Castiglioni, Andrea Celli, and Vianney Perchet. Feature-based online bilateral trade. The Thirteenth International Conference on Learning Representations, 2025.

---

Ilya Hajiaghayi, MohammadTaghi Hajiaghayi, Gary Peng, and Suho Shin. Cains-from-trade in bilateral trade with a broker. In Proceedings of the 2025 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 4827-4860. SIAM, 2025.
Yuan Deng, Jieming Mao, Balasubramanian Sivan, Kangning Wang, and Jinzhao Wu. Approximately efficient bilateral trade with samples. arXiv preprint arXiv:2502. 2025.
Roger B Myerson and Mark A Satterthwaite. Efficient mechanisms for bilateral trading. Journal of economic theory, 29(2)266--281, 1983.
Paul Milgrom and lya Segal. Envelope theorems for arbitrary choice sets. Econometrica, 70(2):
583-601, 2002.
F. Y. Edgeworth. The mathematical theory of banking. Journal of the Royal Statistical Society, 51(1): 113-127, 1888. ISSN 09528385.
Tsan-Ming Choi, editor. Handbook of Newsvendor Problems. Models, Extensions and Applications. Springer, New York, NY, 2012.
Mahmut Parlar. Game theoretic analysis of the substitutable product inventory problem with random demands. Naval Res. Logist., 35(3):397-409, 1988. ISSN 0894-069X.
Steven A. Lippman and Kevin F. McCardle. The competitive newsboy. Operations Research, 45(1): 54-65, 1997.
Siddharth Mahajan and Garrett van Ryzin, Inventory competition under dynamic consumer choice. Oper. Res., 4965)6646-657, 2001. ISSN 0030-364X.
Serguei Netessine, Nils Rudi, and Yunzeng Wang. Inventory competition and incentives to back-order. IIE Transactions, 38(1 0:883-902, 2006.
Yunzeng Wang and Yigal Gerchak. Capacity games in assembly systems with uncertain demand. Manufacturing & Service Operations Management, 5(3):252-267, 2003.
Martin A. Lariviere and Evan L. Porteus. Selling to the newsvendor: analysis of price-only
contracts. Manufacturing & Service Operations Management, 3(4):293-305, 2001.
Elodie Adida and Victor DeMiguel. Supply chain competition with multiple manufacturers and retailers. Oper. Res., 1411::156172, 2011. ISSN 0030-364X.
Gérard P. Cachon and Serguei Netessine. Game theory in supply chain analysis, chapter 8, pages 200-233. INFORMS, Online, 2006.
Lena Silbermayr. A review of non-cooperative newsvendor games with horizontal inventory interac- tions. Omega, 92:102148, 2020. ISSN 0305-0483.
Riccardo Colini-Baldesee Baldeschi, Bart de Keijzer, Stefano Leonardi, and Stefano Turchetta. Approximately efficient double auctions with strong budget balance. In ACM-SIAM Symposium on Discrete Algorithmss, SODA 16, pages 1424-1443, USA, 2016. SIAM.
Riccardo Colini-Baldesehe Paul W. Goldberg, Bart de Keijzer, Stefano Leonardi, and Stefano Turchetta. Fixed price approximability of the optimal gain from trade. In Web and Internet Economics, WINE'17, 17, volume 10660 of Lecture Notes in Computer Science, pages 146-160, Germany, 2017. Springer.
Liad Blumrosen and Yehonatan Mizrahi. Approximating gains-from-trade in bilateral trading, In Web and Internet Economics, WINE' 16, volume 10123 of Lecture Notes in Computer Science, pages 400-413 Germany, 2016. Springer.
Johannes Brustle, Yang Cai, Fa Wu, and Mingfei Zhao. Approximating gains from trade in two-sided markets via simple mechanisms. In Proceedings of the 2017 ACM Conference on Economics and Computation, EC '17 page 589-590, New York, NY, USA, 2017. Association for Computing Machinery, ISBN 978 9781450345279.
12

---

Riccardo
Paul W Goldberg, Bart de Keijzer, Stefano Leonardi, Tim Roughgar- den, and Stefano Turchetta. Approximately efficient two-sided combinatorial auctions. ACM Transactions Economics and Computation (TEAC), 8(1):1-29, 2020.
Moshe Babaioff, Kira Goldner, and Yannai A. Gonczarowski. Bulow-klempereed klemperer-style results for welfare maximization in two-sided markets. In Proceedings of the Thirty-Firss Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 20, page 2452 2471, USA, 2020. Society for Industrial and Applied Mathematics.
Paul Dütting, Federico Fusco, Philip Lazos, Stefano Leonardi, and Rebecca Reiffenhäuser. Efficient two-sided markets with limited information. In Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing, STOC 2021, page 1452-1465, New York, NY, USA, 2021. Association for Computing Machinery. ISBN 978 9781450385539.
Yuan Deng, Jieming Mao, Balasubramanian Sivan, and Kangning Wang. Approximately efficient bilateral trade. In STOC, pages 718-721, Italy, 2022. ACM.
Zi Yang Kang, Francisco Pernice, and Jan Vondrák. Fixed-price approximations in bilateral trade. In Proceedings of the 2022 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 2964-2985. Alexandria, VA, USA, 2022. SIAM, Society for Industrial and Applied Mathematics.
Thomas Archbold, Bart de Keijzer, and Carmine Ventre. Non-obvious manipulability for single- parameter agents and bilateral trade. In Proceedings of the 2023 International Conference on Autonomous Agents and Multiagent Systems, pages 2107-2115, USA, 2023. International Founda- tion for Autonomous Agents and Multiagent Systems.
Francesco Bacchiocchi, Matteo Castiglioni, Roberto Colomboni, and Alberto Marchesi. Online bilateral trade with minimal feedback: Don't waste seller's 's time. In The Thirty-ninth Annual Conference on Neural Information Processing Systems, 2025.
François Bachoc, Tommaso Cesari, and Roberto Colomboni. A parametric contextual online learning theory of brokerage. In Forty-second International Conference on Machine Learning, 2025a.
François Bachoc, Tommaso Cesari, and Roberto Colomboni. A tight regret analysis of non non-nonnaae parametric repeated contextual brokerage. In Proceedings of The 28th International Conference Artificial Intelligence and Statistics, Proceedings of Machine Learning Research. PMLR, 03-05 05 May 2025b.
Tommaso Cesari and Roberto Colomboni. An online learning theory of trading-volume maximization. In The Thirteenth International Conference on Learning Representations, 2025.
Houshuang Chen, Yaonan Jin, Pinyan Lu, and Chihao Zhang. Tight regret bounds for fxed-price bilateral trade. arXiv preprint arXiv:2504.04349, 2025.
Anna Lunghi, Matteo Castiglioni, and Alberto Marchesi. Better regret rates in bilateral trade via sublinear budget violation. In Proceedings of the 2026 Annual ACM-SIAM Symposium on Discrete Algorithms, 2026.
Moshe Babaioff, Amitai Frey, and Noam Nisan. Learning to maximize gains from trade in small markets. In Proceedings of the 25th ACM Conference on Economics and Computation, pages 195-195, 2024.
Anna Lunghi, Matteo Castiglioni, and Alberto Marchesi. Online two-sided markets: Many buyers enhance learning. arXiv preprint arXiv:2503.01529, 2025.
Nicolò Cesa-Bianchi, Roberto Colomboni, and Maximilian Kasy. Adaptive maximization of social welfare. Econometricu, 9333):0033-104,, 2025.
Tommaso R Cesari and Roberto Colomboni. A nearest neighbor characterization Lebesgue points in metric measure spaces. Mathematical Statistics and Learning, 3(1):71-112, 2021.
13

---

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: All claims made in the abstract and introduction supported by theorems and formal proofs in the main part and appendix this paper.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
is fine to include aspirational goals as motivation as long as is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations the work performed by the authors?
Answer: [Yes]
Justification:
The limitations are discussed in Section 7
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create a separate "Limitations" section their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g.. independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution is low images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't 't acknowledged judgment and recognize that individual actions in favor of transparency play impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
the paper. The authors should use their best
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]
14

---

Justification: See Theorems
2.1
3.3
4.1 and 5.1 and corresponding proofs.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced the statement of any theorems.
The proofs can either appear the main paper or the supplemental material, but they appear in the supplemental material, the authors are encouraged to provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental result reproducibility
Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that it affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Question:
Answer: [Yes]
we run an implementation of Algo- rithm (as presented in Section 3) over fully specified and reproducible instances.
Justification: In the Experiments section (Section 6
Guidelines:
The answer NA means that the paper does include experiments. If the paper includes experiments, No answer this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is novel architecture, describing the architecture fully might suffice, or if the contribution is a specific model and empirical evaluation, it may be necessary to either make possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g.. in the case of large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make it clear how reproduce that algorithm. (b) If the contribution is primarily the architecture clearly and fully.
model architecture, the paper should describe
(c) If the contribution is new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome deseribe the particular way they provide for reproducibility, In the case of closed-source models, it may be that access to the model is limited in some way (e.g., registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
15

---

Answer: [Yes]
Justification:
We provide the code and explain how to run it.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips.cm
ooiiioionoly for more details.
While we encourage the release of code and data, we understand that this might not be possible, so "No" an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https
/ ccpppp.ccppulli//guiii wwwtii/gguie///eeeeceoocc CoodeSubeiiieeee ssi wswonnolli onnolicy)))) for more details.
The authors should provide instructions on data access and preparation, including how access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
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: [Yes]
Justification:
All experimental details are described in Section
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, or as supplemental material.
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: [Yes]
Justification:
All experimental details are described in Section
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, statistical significance tests, at least for the experiments that support main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call a library function, bootstrap, etc.)
The assumptions made should be given (e.g.. Normally distributed errors).
should be clear whether the error bar is the standard deviation the standard error of the mean.
16

---

It is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out range (e.g. negative enror rates).
If error bars reported in tables plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables the text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of exccution) needed to reproduce the experiments?
Question:
Answer: [Yes]
Justification:
All experimental details are described in Section
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount compute required for each of the individual experimental runs well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make into the paper).
9. Code of ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurlPS Code of Ethics httts://neurr wwtphhrrrrpps.ppppceeecepcecpeee http//uullc/Ehiieccc csluidelnes!
Answer: [Yes]
Justification: The research conducted this paper fully conforms to the NeurIPS Code of Ethics. There are no ethical concerns related to data collection, experiments, or other aspects of the work, as it focuses primarily on theoretical analysis.
Guidelines:
The answer NA means that the authors have reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special cireumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., if there is a special consid- eration due to laws or regulations their jurisdiction).
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: This paper focuses on theoretical advancements in sequential decision-making and does not have direct societal applications. As such, does not explicitly discuss potential positive or negative societal impacts. The work is foundational in nature and does not involve technologies that could be misused or present ethical concerns in its current form. Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No. they should explain why their work has no societal impact or why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
17

---

The conference expects that many papers will be foundational research and not tied particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition attacks, mechanisms for monitoring misuse, mechanisms to monitor how system Iearns from feedback over time, improving the efficiency and accessibility ML).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data or models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification: This paper focuses thcoretical algorithmic advancements in online learning and does not involve the release of models, data, or other resources that could pose risks for misuse. Therefore, safeguards necessary, there is high-risk data models associated with the work.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have a high risk for misuse or dual- use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Question:
Are the creators or original owners of assets (c.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: No assets have been used.
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms use in package should be provided. For popular datasets, paperswithcode com/ datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
18

---

For existing datasets that are re-packaged, both the original license and the license of the derived asset (if has changed) should be provided.
If this information is not available online, the authors are encouraged to reach out to the asset's s creators.
13. New assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer:
[NA]
Justification:
No assets have been created.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/model as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset used.
At submission time, remember to anonymize your assets (if applicable). You can either create anonymized URL or include anonymized zip file.
14. Crowdsourcing and research with human subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well as details about compensation (if any)?
Answer: [NA]
Justification: [NA]
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According the NeurIPS Code of Bthies, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
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 or institution) were obtained?
Answer: [NA]
Justification: [NA]
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurlPS Code of Ethics and the guidelines for their institution.
For initial submissions, not include any information that would break anonymity (if applicable), such the institution conducting the review.
19

---

16. Declaration of LLM usage
Does the paper describe the usage of LLMs if it 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, or formatting purposes and does not impact the core methodology. scientific rigorousness, originality of the research, declaration is not required.
Question:
Answer: [No]
Justification: The core method development in this research does not involve LLMs as any important, original, or non-standard components.
Guidelines:
The answer NA means that the core method development in this research does not involve LLMs as any important, original, or non-standard components.
Please refer to our LLM policy buctps://neure wwwparippps..coooeeeeeeeee for what should or should be described.
20

---

A RMNP is a generalization of bilateral trade (For Section 1)
Theorem A.I. The repeated mediated newsvendor problem is a proper generalization of the repeated bilateral trade problem.
Proof. To prove this claim, it suffices to show that any instance of the bilateral trade problem can be mapped to an instance of the RMNP such that the feedback and reward under both environments is identical.
To do this, consider an arbitrary instance of the bilateral trade problem, denoted by (Sc, Be)teN. We define a corresponding instance (Ct, Ut)LeN of the RMNP follows: Vt E N. let C2 == S; and let U, E USC be defined, Vig E [0, 1], by Ut(g)= = Be q.
First, we observe that the associated RMNP problem has the same action space [0, 1] as the bilateral trade problem.
Next, we show that, for any posted price E [0, 1). the learner receives the same feedback under the instance (Ct, Un)TEN as under (S,, B, B.NN
Suppose that the learner posts a trading price p E [0, 1] at time / E N. Then, in the case of bilateral trade, the learner observes 1(S, S p} from the seller and 1(p < B₂} from the buyer. In the corresponding RMNP instance, the learner observes U[C, S p} = 1(s S p} from the supplier and
{1) if < Bt.
(p( (p)
argmax (U)(1) - p- 9) = argmax (B. 9 pp ge/u.1]
ifp B [0,
{0)
gE/0,1]
p B.
from the retailer. we assume that in the case of tie (i.e., B, = p), the retailer selects the maximum quantity possible, namely 1, then the observed feedback is precisely
{1
i B
U (p) max argmax (U,(g) -p.9) 1 ye[0.1]
IIp B,). if Bt
Thus, the feedback received under (Ce, UN)EN is identical to that received under (Se, Be)ENN- Finally, we show that the reward function under (C,, UL)EN the same as the reward function under (S,, B,)tEN.
Fix any p [0, 1] and any / N. In the case of the bilateral trade problem, the reward function under (St, BeJtN is defined as
GF S,, B,) = (B, - S.) S p B.}.
In the case of the RMNP. the reward function under (Ct, Ut)EN is defined as
g(p, C., Ut) = (p- -.) (p) + U7 (p())) I[C, s).
Now, for every p E [0,1], 1]. observe that (p = Us ( (p) - U (p) = B, U.# - pp (B--)) B.).
Hence,
g(p, C., U.) = - Ct) U.) T[C, sp)
((p S,) < B,) +
s B,)) IKS, s}
= (B, (B,-S))lpp= < B, <p}
=(B, (S) <p Bi}
= GF, B.).
Therefore, the reward function under (Ct, Ut)tEN is identical to that under (St, B.)TEN. Since (St. BeeN is an arbitrary instance of the bilateral trade problem, it follows that the bilateral trade problem a special case of the RMNP. Equivalently, the RMNP a proper generalization of the bilateral trade problem.
21

---

B Missing details for Section 2
Theorem B.1 (Theorem 2.1 restated). The mediated newsvendor mechanism is incentive compatible, individually rational, and budget balanced.
Proof. Let be the supplier's cost, the retailer's utility, p the proposed trading price, b the decision disclosed by the supplier at price (1 if accepted, O if refused), and the quantity disclosed by the retailer price p.
Incentive Compatibility. We begin by proving that the mediated newsvendor mechanism is incen- tive compatible.
Supplier's incentive. Consider the supplier's possible decisions:
If b O, the supplier gains nothing. However, if p, the supplier could achieve positive gains by accepting the trade, i.e., by reporting b = 1. Hence, refusing the trade when c < p can only decrease the supplier's 's net utility.
b = 1, the supplier's 's utility is p- c, which is negative when p < c. contrast, by refusing the trade (i.e., reporting 5 = 0), the utility is zero. Thus, accepting a trade when c can only decrease the supplier's net utility.
Finally, if p p= c, the supplier indifferent between accepting and refusing the trade, as both yield zero utility.
Therefore, reporting truthfully, i.e. T(c S p), is dominant strategy for the supplier.
Retailer's incentive. Next, we show that no deviation from = u# (p) improves the retailer's utility. By definition:
t (D) argmax(u(1)) - p-
eE(o.1]
Thus, for any deviation * # (p). we have:
u( 7 p T u(u" un
Additionally, the retailer's choice quantity 7 does not affect the supplier's acceptance decision, which depends solely the mediator's chosen price p. Therefore, reporting any that deviates from the truthful choice a (p) can only decrease the retailer's utility.
Individual Rationality. Next, show that the mechanism is individually rational for both parties.
Supplier's rationality. The supplier's net utility when a trade does not occur (p < c) is zero, while when trade does occur p), their net utility is:
(gp -0)-c) p} q(p c)l(p 0} 2 0.
Thus, the supplier never incurs negative utility.
Retailer's rationality. Since the retailer selects quantity:
# (p) aargmax((() p p-9); gE[0,1]
it follows that:
u(u# (p)) p- # (p) 2 u(0) - p.p.p. u(0) 2
Thus, the retailer also never incurs negative utility.
Budget Balance. Lastly, we observe that the mechanism is budget balanced: the total amount the retailer pays is exactly the amount transferred to the supplier. Specifically, the supplier receives precisely the retailer's payment # (p).
22

---

C Missing details for Section 3
Lemma C.I (Lemma 3.1 Restated). If USC, then, for any selection of whth and any 0 S Pt < P2 I 116 it holds that
L p1
n' "'(p)) u- (p2)
u (A)
Proof. This is corollary of the celebrated Envelope Theorem Milgrom and Segal 2002]. For completeness, we report a version of this result as Theorem F.1 in Appendix Using the notation from Theorem F.1 define the function f: [0, 1| IR by (g. p) + u(g) pq. We observe that, for every E [0, I,, the function + f').p) is upper semi-continuous (being the sum of two upper semi-continuous functions). Furthermore, the function (g, p) 0p((g.P) -q is continuous. Hence, for any selection x": [0, 1] + [0, 1] satisfying, for all E [0, 1].
x (p) argmax ((q.)), rE(o.1]
the function V: [0, [0, 1}.p max f().p) satisfies, for all p E [0,
(pp) V(0) + [ (p)(
The conclusion then follows by observing the following: for every À E [0, 1]. we have O,f (A), A) = - (A); for every E [0, 1], we have u (p) = Vp)); and for every E [0, 1]. aM
is a selection satisfying w (p) E argmax (g.p).
Lemma C.2 (Lemma 3.2 Restated). For any E USC, the functions u² and a# are monotonically
non-increasing.
Proof. From Lemma 3.1 for any S pt < p2 S 1, we have that (pt) = p # (A) dA 2
where the inequality follows from the non-negativity of t This directly implies that u² is monotonically non- non-increasing.
Now, to show that ## is monotonically non-increasing, consider any 0 S < p2 S and let d = # (p:) for = 1,2. Then,
(p2 (p) - 92) = =(u(g2) - P242) - (u(q1) p291) + (u((1) - Piq1) - (u(42) ) P1g2) max (u(q) p29) - (u(g1) P291) + max (u(g) P19) (u(q1) PP111) gE(0,1)
gE[0.1]
20
0, and the conclusion follows upon dividing by p2 p1 0.
Theorem C.3 (Theorem Restated), Assume that Assumptions T.I-1.4 hold. If Algorithml 7
with time horizon T, discretization parameter K == /3 and confidence parameter d == +. then
R₂ = 2/3
Proof. Define, for any p f(p) E E[g(p. C,U)]. Recalling Assumption 1.1 for any time horizon T E N, we define the pseudo-regret Ry suffered by a sequence of prices PT Pr to the time horizon T N as
RI Σ
sup f()) - S(P)) pE|0.1]
Then, after a straightforward application of the Freezing Lemma F.2 obtain that Ry E [Ry]. This observation suggests studying the pseudo-regret to prove the regret bounds.
To prove the theorem, without any loss of generality, cally, we notice that the crude bound 2 5 107 suffices for the following calculations. We leave the optimization of the involved constants to the interested reader.
may assume T is sufficiently large. Specifi-
23

---

Let K E N with 2 S K and K² < T. We may assume that (C₁, Ut) is generated in the following way. Consider two i..d. families that are independent of each other. For every E N and every, {0, .,....... K 1}. the distribution of the pair (Cr,j, U(.) is identical to the distribution of (C,U), At time = 1, we set
and (ee.))e (0......K
(C1, U1) = (Cx,, (0),11 UN, (0),1.).
Then, inductively, at each time 1+ E N, when the algorithm selects the index 4441 E (0, ,,...,K K 1}, we set
(C.+1, = (CN,, (000(1))))))))
By induction, the sequence (Ce, Uc)eN is well-defined. Moreover, this sequence is i.i.d., and the distribution of (C,, Ut) coincides with that of (C,U) for every E N.
Now, notice that by applying Assumption
1.2. for every p [0, 1]. obtain that
f()) = E # (p) E (p - c)+| + E [CC S B[)*)))
Then, for any j E {0, 10. K - 1). i E [p., Pj p]+1|, leveraging Lemma 3.2
we have that
f()) - f(,)) E (p) BBOo-CTT-B((>- +)+)
+ + (p) - (p,) (D)
+ (B|LkD) <0 S p} [U)
+ Elu[C spiil
E (B("))) U
20
1 + m
s (p - p,) + mlp pj)
K
where in the second-to-last inequality used Assumption 1.3
and in the last inequality used the
fact that S Pj+1 Pj = 1/K.
Hence, for each k {0,1...., K 1}. by setting A == ma. --1) f(P)) f(P)) and
noticing that suppe(o.1) f(p) - f((P)) < 1, we have that
Rr < R2 +
Σ
sup f(p) S(P?) pE/0..1]
t=
(1 + m)T
T
< K2 +
max
f(p,) - f(p1.)
K
JEfo.I....K-1))
t= R2-1
(1 m)T
K2
A
1= 12
To declutter the notation, for each j {0, I,..., K 1}. define a, = =E 8, E[1(C's
p. ęPx = [p;)] and wi = [p,; - C++ Notice that, for every j E (0, 1,,,, K - 1}. we
have that
f(p,) a, 3/ By P4
Recall that for any USC and price p E [0, 1]. ## (p) argmax (0 (u(2) p q), so can consider the family (U (...
24

---

Now consider the "bad" events-event events in which the estimators we defined are far from the value they aim estimate estimate-definet for any E (0, 1) and j E {O.1.....A 1}. by
1 K
Eg,6,
(p.) -3/ 2 SK.B
Ev,6,
H[ S pi) -ws 2 GKo
K
and for any 8 (0,1),5 f0.1..... K - 1}, and n E N, by
U (p,) -as 2 2
Ea,5mn =
I[Ck. ST}} 33 2 Sm.aool
Moreover, for every 8 E (0, 1), define the global "bad" event
K-1
Eg = U
CesssUEn U (Ea U UEgans) n=k
==0
Now, make two crucial claims. First, for every 8 E (0, 1), we have that
P P|Es] < 8.
(I)
Second, for any 8 E (0, when we are in the complement of the global "bad" event &s, we have that, for every j E {0, l..... ., - 1} and every t {K2 + 1, + ,,.....27 T}.
2ln (SKT) 16
f(p,) S -1-1(1) - f(p,)
(2)
min WN,(t - 1), K)
whenever
8 2 8K max
Te K/8 - -2(1/2211)))
-K/8
(3)
and
8TK
88K
2 In
2 21+ 21n
(4)
To aid readability, we defer the proofs of these claims until after the end of this proof.
Now, when we are in the complement of the global "bad" event Eg, assuming that conditions and hold, it follows from Equation (2) that for every E {K² + K,2 ,,...,TT: T).
max SE(O,I....KI1) K-1) f(P,) S
max Je(0,1,...KK]
1 11+)
16 /6/210 21n (SKTT)
s(pr)) + min ( // (1 (1-,,,,)
and consequently,
16 2 In 8KT
A
min / NN - 1), K
Thus, when we are the complement of the global "bad" event Es. and conditions and hold, we have that
T
K-1
T
Σ
D
Σ
Σ
A,,l4 = k}
t=
K
k=
t=
25

---

K-1 I
Σ
Σ
A,44 - - K2}
++
K-1 T
Σ
Σ
-, <3}
1=K++1
8KT
14=k)
16 2ln
5
K
41
(KT
14 k}
+ 16
2 In
8
V Nt, 1)
K241
K-1 (2)
8KT
T
8KT
16
2ln
+ 16
2ln
8
K
vi
8KT 8
T
8KT
K
16
2
+ 16
2ln
2 (T)
K
A
(KT'' 8
T
16
2ln
2v KT
KT
K
where the last inequality follows from Jensen's inequality. Hence, noticing that Ry S S, when 3 and hold, we conclude that
Br=E(RT] [[(TTE, + B[RrTegg]
(1 + m)T
8KT
T
< <TF[E& + k +
+ 16
2lm
+2VKT
K
8
K
(1 + m)T
8KT
T
T8 K2
+ 16
2
++2VK7
KT
K
5
K
Now, if we K / and ` +. recalling that T 2 5 107, have that and hold, and the conclusion follows by simple estimations.
To conclude the proof of Theorem 3.3 we now present the proof the two missing claims 1 and that used in the proof of Theorem 3.3
26

---

Proof of claim that
① For any E {K² + 12 + ....... and any j jE {0, 1O... K - 17, we have
K
K-
(g,( - Pj
K
K
K-1
U (pt) E U (py))
ΣΣ
K
(P.)
E
U (ta))a)))
ps
E [ (ttiosaa))
(P.)
Up dal - (/m U uttwaaa))
E
(P.) dA - E [f U (tssesa)))
pit
(2)) di (x).
+E
Σ
(p:)
Additionally, since U# is monotonically non-increasing (see Lemma 3.2. using telescopic argument, we have that
K-1
Pit1
0
-U*()))U*())) (A)) ad
P1
(U*(p)) U (pi+1)) ad
U# -
1
Σ (U# (p:) - U (p:+1))
5
K
K
K
It directly follows that
K-1
Pitt
(P) [m U (tt +
1(+) E
Di
K-1
[[j (
Pits
(Etl))a)))) 1
ΣΣ
(p. dd - E 11j [1
1=1 1=
1
(0) +
K
27

---

Hence,
1
K-1
1 v 2ln(8K/0)
IP [.p = P
UK 93
2 CK.5
= P
[x)
K
K
|=)
1
1
v 22nn(8K88)
PP
(0) +
2 +
K
K
K
K
P
1 i
1=
pit) _ (tsss))))) 22ln(8K/6)
E
Noting that the last probability involves the of K2 zero- independent [- | random variables, the previous inequality, together with Hoeffding's incquality, implies that
(222((8/8)
8
Pl exp
K². K
4K
Analogously, we can prove that for any t E {K² + 1, K2 + 2..... 7) and any j E 10,1,.... K
... K-1}. 1}.
P E S
4K
K 13, we have that Moreover, for any n E {K, K + 1.... T} and any j E {0, 1,
1
P = P
2 (T,K((()) Nig (p:) ag
( (p))) | (n))))
P
2n In(K8/888
where the last probability involves the sum of n zero-mean independent [-1, 1]-valued random variables. Thus, once again by Hoeffding's 's inequality, we have that
(2
Pl s 2exp
4n
4KT
An analogous argument, for any n {K, K 1, I,..., T} and any j E {0, 1,.,, K 1}. shows that
2 (nlKK(87/85
P[Eg,an.)] < eexp
4n
4KT
Finally, using union bound, we obtain that
Epe U (Ea,s.m U Eassms)) )
P|E P
P(Ep.8.) + PP(
Σ
+
Σ
P(ga.mmm))
n=k
n=k
8
6
8
8
<
4K
4K
4KT
4KT
which concludes the proof of claim I
28

---

Proof of claim 2 To prove claim 2 we assume from this point onward that we are in the comple- ment of the global "bad" event Eg and that conditions 3 and 4 hold. For any j E {0, ......... K 1}
and any / E R + 1, K2 2, 7), we have that
{(2) aj 44 + +33 9B3-9p P3s
k=1 k.j (Ps)
(2(t-1)
(1
K
j-1
+ (
HO S ps} + CK.6
Ny(t 1)
K²
Arm
==0
2 1) [[Cn SPi +5Txx((3((-111))
K K-1
Σ k=
(p:)) + SxC,6
1))
K2
1=3
AN ( + (NT
(G, (G,+ + 5k,5)
NU(t 11(t-1)
By (N, (t-1))
Ng(1 11 + ST,KK 11) (Fg + Ck,))
9 (
1) t (p)
K
i-1
kkl
+ ((Txo(N((t-11))
1
HO S Pp} + SK.6
N₂(1 1)
K2
12(1-11 (1CKSSPi + ( k=1
1
K
K-1
(ps) + CK,
1)(1-1)
K2
< (ay + 2. (Ny(t- (65-1)) 1))) (1b + 2CK,)) + (3) + 2, (N, (t-1)))) (19) + 25x,6)
م + #Bj4z + 88 (SK, + &T,K.& (N₂(1 1))) (p3) + (Sx. + ET,K, (N₂(1 - 1)))
f(()) + 16 In (SKTT
min
Nt - 1),
where in the second-to-las inequality, we used the fact that ay .3, 9g 1b E [0. and that 2K.8. 25T, K.s E [0. 1] (by condition 3), and in the last inequality, we used Equation (4) concluding the proof of claim 2
D Missing details for Section 4
Theorem D.I (Theorem 4.1 Restated). Assume that Assumptions L. 1.4 hold. Then, the worst-case
regret of any algorithu satisfies
R = 2((T233)
Proof. In Appendix A we show how associate every instance (S,, B:)EEN of the bilateral trade problem with a corresponding instance (C,, UN)eN of the RMNP such that, for any price posted by the learner, the feedback and reward remain identical. Moreover, we notice that this correspondence satisfies the following equivalences:
A. (St, Be)teN is independent and only if (C,, UN) is independent.
B. (St, B.)teN is an identically distributed stochastic process and only (C,, U.)EN is an identically distributed stochastic process.
C. For all t N, St and B, are independent if and only if C, and U, are independent.
D. For all & E N, S; has a m-bounded density (i.e., has a m-Llisschiz edf) if and only if C, has m--ounded density (i.c., it has m-Lipschitz edf).
29

---

Consider the RMNP under Assumptions I.] 1.4
Suppose, by contradiction, that there exists learner's s strategy a that achieves a regret strictly less than 2/2/3 for all instances of this problem, where e 11/672.
Now, consider an arbitrary instance of repeated bilateral trade (St, Be) where the sequence an i..d. stochastic process (iid) and, for every t N, St and B, independent (iv) and admit densities bounded by m 2 24 (bd). By the reduction established in Appendix A there exists a corresponding instance of the RMNP, denoted by (C,, UI) We observe that, by properties A and B, the sequence (C,, UN) is an i.i.d. stochastic process, satisfying Assumption 1.1 Additionally, by property C, C and U2 are independent for all N, satisfying Assumption 1.2] Furthermore, property D implies that for all i E N, C2 admits an m-bounded density, which in turn implies that its edf is mmpsciicii thus, Assumption 1.3 is satisfied. Finally, by the structure of the reduction described in Appendix Assumption i.4 also satisfied:
(B. 1)-0 if B, VIE,, (* = (B. - 1)T(1 S B₂) 00-1
= B
Thus, (C,, Uc)eN is instance of the RMNP satisfying Assumptions L.I 1.4 and therefore, by assumption, achieves a regret of less than 2/2/3 under (C2, Ui)te
However, since the feedback and reward under (St, Bi)tEN and under (C,, sE are identical (as shown in Appendix A). must also achieve regret strictly less than cT2/3 when run on the bilateral trade instance (St, B.)tEN. Since (S,, B.)xeN was chosen arbitrarily from the class of repeated bilateral trade instances satisfying the (lid), (iv), and (bd) assumptions, this conclusion holds for all instances in the class. This result contradicts the minimax lower bound established in al. 2021 Theorem 4.4] (see Appendix IF). which states that no learner's ' strategy can achieve regret below 2/2/3 3 for all instances of the repeated bilateral trade problem satisfying these assumptions.
Thus, no learner's strategy can achieve regret strictly less than 2/2/3 across all instances of the RMNP satisfying Assumptions I.I Consequently, the worst-case regret of any algorithm satisfies Rr = (T2/3).
E Missing details for Section 5
Theorem E.1 (Theorem 5.1 Restated). Assume that at least one of Assumptions/ 1.1 L. hold. Then, even if the remaining three hold, the worst-case regret of any algorithm satisfies
does not
Ry = (TT).
Proof. We prove this statement by showing that relaxing any one of the four assumptions, while maintaining the other three, leads linear regret.
We first show that any algorithm suffers linear regret when Assump- tion 1.2 is relaxed As detailed below, this is due to bcc--of-observabill phenomenon: we construct two environments, fr and v. which are indistinguishable from the learner's perspective but have distinct optimal and (highly) suboptimal regions.
Relaxing Assumption 1.2
To do this, let [=z)20)0 be the family of utility functions defined, for every x E [0, 1), by
Uz (g) xlig = =
Observe that each utility function u is uniquely determined by the value x uz (1).
This proof is adaption of the proof sketch of Theorem 4.5 Aasa-Bianchi et al. 2021
30

---

We then define the following product sets in the space of cost-utility pairs:
3 1
R1
0,
X
Up
2
2
3
7
R2
Uw
88" 1
8
8
4 5
5 6
R3
8 8'8
Ur
88'8
along with their mirror reflections across the anti-diagonal, defined by the transformation T [0, 1] x {2x]=e)0,11 + [0, 1] x {ur)=eju.a), (c, un) + (1 2, u1
R4 T(a)), Rs (R2), Rs T(R3)-
We let ri...., To denote uniform (product) measures on R1, ....... Ro, respectively, and characterize our two environments by
= (1 + 22 ts), v: u (ra + rs re).
We now consider sequence of supplier costs and retailer utilities (C,U), (C1, U1), (C2,U2),.. U2).... drawn from either a or v.
When the underlying distribution is μ. the expected gain from trade p + E [g(p, C, C]] is uniquely
maximized at g. and if p E [ 1]. then
S - Ct, 12
Symmetrically, when the underlying distribution v, the expected gain from trade is uniquely maximized at 3. and if E [0, 5 then
8 Cr U.) -E
2 12"
All that remains is show that, for every price p E J0. 1]. the feedback (I(C S p}, Up)) (I{C & Ipp & U(1))) is indistinguishable under the distributions fu and v.
We can notice that the feedback observed indicates which block the pair (C, U) lies in:
Boo(p) {(c, u) c p, u(1) p}. Bio(p) = u(c,u) c p. u(1) < ph.
(o) ((c,u) p, u(1) 2 p). Bu(p) = (c,,u) : c S p, w(1) 2 p).
By direct verification,
T(B - p)) Boo(p), T(B1o(1 - (p) = (p).p).
T(Boi(1 - -p) B1O(P), T(Bn(1 - p)) = =B1(p).
Hence, for any (i,j) (0,1)3
1 (BB((D)) = p (B.(() (B -1B p)) = (B;;
where the last equality follows by the symmetry of the rectangles. Consequently. the distribution of the feedback is identical under both μ and v.
Thus, any learner's strategy must perform sub-optimally in least half of the rounds within one of the two indistinguishable worlds. Since the loss suffered in each sub-optimal round is at least 1
T2. the
expected per-round regret is least 1
24
Therefore, conclude that the regret of any learner's strategy is at least L..
31

---

construct an Relaxing Assumption 1.1 We now adapt the above construction to show that linear regret is inevitable when Assumption 1.1 is relaxed Specifically, we introduce two families of oblivious adversarial environments, Fr and Fu. each generating sequences of independent (but not necessarily identically distributed) cost-utility pairs. We then show that the worst-case regret suffered by any learner's s strategy under environments from J₁, 4 or Fy is at least as large as the regret suffered under Iu or v, respectively.
Recalling that, for every i = .,..,, 6, the distribution Ty is defined as the uniform measure on the product set Rg. we now construct the two adversarial families:
T mi (M))uT E (1,2,3)7 Fu =
{
X ri (Fe)eet E (4,5,6)* A
Now, for any learner's 's strategy, the regret suffered against the worst adversary in Fr is lower bounded by the (expected) regret the learner suffers when the adversary is selected uniformly at random from the family Fu. Choosing this adversary uniformly at random from F₁ is equivalent independently and uniformly selecting each index ét from {1, 3). This yields a sequence of cost-utility pairs (Cs, U)) (C2, U2), whose marginal distribution each round is precisely μ..
Hence, the maximum regret any learner's strategy suffers from an adversary in F₁, is at least as large as the regret suffered under the environment
Analogously, one show that an adversary chosen uniformly at random from F, is distributed according to v. Thus, the maximum regret any learner's 's strategy suffers from an adversary in Fu is least large as the regret suffered under the environment V.
Combining these results, we can conclude that the regret of any learner's strategy is at least 24 T.
Relaxing Assumption 1.3 To show linear regret when lifting Assumption I.3
infinite family of i.i.d. environments,
{uz x1l
and show that any learner's 's strategy suffers linear regret under at least environment in this family To do this, for every x E [ 3]. we define two [o. 1] valued utility functions
M (q) = x xI(4- 1},
"1 "I(a) Ifq 1}.
Then, letting & be the Dirac measure on x, we set
fx == 1 60 + 1 2 6u. + + 5m.)
Under the environment Ma, the expected gain from trade is uniquely maximized p and if p # x, we have that
Elg(z, C,U) - C,U)) min (ar 1 x.
2 4 10
where the inequality follows from the fact that x [ 5
Since this environment is stochastic, without any loss of generality, it is enough to show that deterministic algorithms suffer linear regret. Fix arbitrary deterministic algorithm and time horizon E N. Let Pi...., Pr denote the sequence of posted prices. Since the interval is uncountable, there exists some
1' (pI...,,PTh
Under the environment plat, the price x' is never posted. Thus, for any sequence of supplier costs and retailer utilities (C1, U1), (C2, U2) drawn from par inequality ( holds at every round E [T]. implying that
E B[o(z', C. G.UU - Cr, U.)]
10"
Summing over 1. 1,..., yields regret of least 112 T.
TThis proof an adaption the proof of Theorem Cesa- Bianchi 2024 'This proof is adaption of the proof of Theorem 4.6 Cesa Bianchi
202
32

---

Finally, we show that no leamer's strategy can achieve sublinear worst- case regret without prior knowledge of (a)) for some price a E [0. 1], even when the first three assumptions 1.1 1.3 still hold.
Relaxing Assumption 1.4
Define the two functions
f: [; + [0,
q -q 0.7) + 0.5,
h: [0, 10
- (q 0.7) + 0.65.
Then, letting be the Lebesgue measure on [0, 1]. we define
X 8y.
X 2 5n.
Suppose that the sequence of supplier costs and retailer utility functions (C,U), (C1, U2)....... is drawn i.i.d. from or V.
When the underlying distribution is μ. the expected gain from trade - E [p(,, C, is uniquely
maximized at 7, and if E [ 1]. then
7 Cr, - Elo(, C,, U.) 2
E
2500
On the other hand, when the underlying distribution is v, the expected gain from trade is uniquely maximized at p 14' and if E [0, ]. then
13 C. v.)] -E[(pp C. U.) 2 4000
E
g
14
Under both distributions μ and v, we have (p) 0.7 - for every price p [0, 1]. Hence, the feedback (I{C) & p}, (p)) identical under both distributions, making the two cases indistin- guishable to the learner.
Thus, any learner's strategy must perform sub-optimally in least half of the rounds within one of the two indistinguishable worlds. Since the loss suffered in each sub-optimal round is at least
min (2500 2000): the expected per-round regret is at least min 2500 1000 5000
Therefore, conclude that the regret of any learner's strategy is at least 5000 T.
Other results
The following is direct consequence of Corollary 4 of Milgrom and Segall 20022]
Theorem F.1 (Envelope Theorem, Milgrom and Segal 2002). Assume that f: [0, 1 + [0, 1] is such that
for all E [0, 1}. we have that the function + [(g.p) is upper semi-continuous.
for all E [0, 1), we have that the function (g.p) + (p.(p) is continuous.
then, if we define
V: [0,0
+ max f(g. p) gE[0,]]
and x= :00, [0, any selection such that for any p E [0, 1},
xp) argmax f(g.p)
qE(o,1]
we have that x is integrable, and, for any [0.
V(p) = V(0) + f x (A)
33

---

For completeness, we also report the freezing lemma (see, e.g., Cesari and Colomboni [202T] that we use in the proof of Theorem 3.3 to convert pseudo-regret guarantees into regret guarantees.
Lemma F.2 (The freezing lemma). Let (St F, IP) be a probubility spuce. Let (V, and FwFw)
be two measurable spaces. Let f V x W - [0, [0,+ Ω + V, W Ω + W be three
measurable functions. V and W are P-independent, then
EE W) V [E[s(v, Willomv
P-almost surely, where the right-hand side is the composition
[B]f(e, Willuzv = (o B[f(v, V...
Moreover, we report the repeated bilateral trade regret lower bound theorem [Cesa-Bianee) et al. 202T Theorem 4.4] that we use the proof of Theorem 4.1 to establish the optimality of Algorithm for the RMNP.
Theorem F.3 (Theorem 4.1, Cesa-Bianch Bianchi et al. 2021). In the realistic-feedbac model, for all
horizons the minimax regret R7 satisfies
R = inf sup (S,B)~D
Rr(a) 2 2T2/3
where c 2 11/672. the infinum over all of the learner's strategies a, and the supremum is over all distributions of the seller S and buyer B such that:
(iid) (S1, B1), (S2, B2), (S. B) is an i.i.d. sequence;
(iv) S and B are independent of each other;
(bd) S and B admit densities bounded by m 2 24.
34


Reviews:
[{"review_id": "9AtkK975Sj", "reviewer": "Reviewer_LSey", "summary": "The paper studies an online learning version of the repeated mediated newsvendor problem (RMNP), where a platform (mediator) sets trading prices between suppliers and retailers over time with the goal of maximizing social welfare (gain from trade). At each round, a supplier with a private production cost and a retailer with a private utility function arrive, and the platform proposes a price. The supplier decides whether to accept the price, and if so, the retailer decides how much to purchase. The authors propose a no-regret algorithm that achieves an $\\widetilde{O}(T^{2/3})$ regret rate under four key assumptions: i.i.d. supply and demand, independent supplier and retailer types, Lipschitz supplier cost distribution, and bounded retailer utility at the highest price. They also provide a matching lower bound showing this rate is unimprovable up to log factors, and impossibility results demonstrating that relaxing any of the assumptions leads to linear regret. The paper positions RMNP as a generalization of bilateral trade and provides empirical simulations validating the theoretical results.", "questions": "1) In motivating Assumption 1.1, the paper states: \"The first two assumptions simply mean that this is a stochastic i.i.d. setting in which the supplier’s production cost does not directly influence the retailer’s utility function. This models the real-life fact that the utility earned by the retailer is only directly affected by the trading price.\"\n\nCould the authors clarify the basis for this assertion? What evidence or reasoning supports the assumption that these are independent in realistic settings, beyond analytical convenience?\n\n2) The algorithm forms an overall UCB for gain-from-trade by multiplying UCBs for acceptance probability and surplus given trade. Could the authors clarify whether this product construction maintains the desired confidence level, or whether more direct concentration for the product would be needed to ensure statistical validity?\n\n3) The algorithm relies on a uniform discretization of the price space and spends $T^{2/3}$ periods on pure exploration. Could the authors comment on why they chose this non-adaptive exploration strategy, and whether more efficient alternatives could achieve similar regret guarantees with improved practical efficiency?", "limitations": "Limitations of the work are not properly discussed in the paper.", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 1, "significance": 2, "originality": 3, "strengths_and_weaknesses": "Strengths:\n\n1) The paper provides substantial theoretical results, including a no-regret algorithm with regret guarantees that match a proven lower bound up to logarithmic factors. The impossibility results clearly delineate the boundary between settings where sublinear regret is achievable and where it is not.\n\n2) The formulation of RMNP and its connection to bilateral trade mechanisms represent a novel contribution\n\nWeaknesses:\n\n1) The assumption of independence between supplier cost and retailer utility are quite strong and limit the applicability of the results to real-world mediated markets, where these characteristics are often dependent through shared context. This creates a contradiction with the Motivation section.\n\n2) The problem setting is not clearly described. The formal presentation is difficult to follow, with notation and decomposition choices.\n\n3) The proposed algorithm spends $T^{2/3}$ periods for pure exploration of the pricing grid which is not practical.", "was_revised": true, "final_justification": "The authors have provided technically sound responses that helped clarify my main concerns. In particular, their explanation of the independence assumption, the construction of confidence bounds for gain-from-trade, and the necessity of pure exploration addressed the key technical and modeling issues I had raised. While the assumption of independence still limits applicability, the authors have acknowledged this and suggested a possible contextual extension. That said, I still find the novelty of the work to be moderate, as it builds closely on prior bilateral trade literature. On balance, I am updating my evaluation to a borderline accept.", "rebuttal": "**Can we assume suppliers' costs are independent of retailers' utilities?**\nFair question. A first reason why the assumption is reasonable is related to the distinct economic drivers of suppliers and retailers.\nSupply‑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. \nThese 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.\n\nAnother 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.\nIn 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.\n\nA more technical reason has to do with necessity (not mere convenience) for learnability.\nTheorem 5.1 shows that allowing any statistical dependence between $C$ and $U$ makes sublinear regret unachievable: the optimal benchmark itself becomes unidentifiable. \n\nThat 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. \nThis 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).\nWe conjecture that, due to the contextual nature of this setting, different techniques would be needed to address this extension.\nWe 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.\n\n**UCB and confidence levels.**\nWe 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. \nIn 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. \nThe full derivation can be found in the appendix (it ends at the bottom of page 26).\n\n**Necessity of pure exploration.**\nGreat question! \nWe 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. \nThe 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).\nTo 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.\nThis 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.\nStill, 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.\nAgain, 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. \nThere (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. \nThis essentially amounts to forcing the learner to spend $\\Theta(T^{2/3})$ rounds of \"pure exploration\".\nWe are happy to add this discussion to the revised version as well.\n\n---\n\nWe hope our answers helped clarify all lingering doubts. \n\nIf this is the case, we'd kindly ask the reviewer if they would consider readjusting their score."}, {"review_id": "C3XegSRMVK", "reviewer": "Reviewer_m1KJ", "summary": "This paper studies the repeated newsvendor problem, a game with three players: a supplier, a retailer, and a mediator. Different from literature where the supplier determines the trading price, in this paper, the mediator determines the price to facilitate trades and maximize the social welfare over time. The authors introduce an online learning algorithm for this mediator. Their research offers robust theoretical findings, including highly effective learning rates and matching lower bounds. Additionally, the paper thoroughly examines why certain initial conditions (key assumptions) are essential for the problem's learnability.", "questions": "The mediator's objective is to maximize social welfare. In real-world mediated platforms, other objectives might exist (e.g., maximizing mediator's profit, ensuring fairness between participants). How might changing the mediator's objective function affect the learnability, regret bounds, or even the mechanism design properties?", "limitations": "yes", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 3, "significance": 2, "originality": 3, "strengths_and_weaknesses": "On the positive side, this paper considers a learning approach to maximize the sum of the net gains of the supplier and the retailer during repeated interactions. I found the problem presented by the paper interesting and relevant. In general, this paper proposed an innovative research topic.\n\nOn the other hand, although the necessity of assumptions is technically justified by Theorem 5.1, a deeper intuitive explanation of their real-world meaning would make more sense. For example, what practical situations might violate these assumptions, and how often do such scenarios occur?\n\nThe claim in Theorem 2.1 is not surprising, especially given the i.i.d. assumption for each round's supplier and retailer. Under this assumption, participants naturally have no reason to act dishonestly.\n\nThe paper does not report error bars or other measures of statistical significance for its experimental results. While the experiments illustrate the theoretical findings, providing some indication of variability or confidence intervals (e.g., shaded error bars in Figure 1) would improve the credibility of the empirical results and align with standard reporting guidelines.\n\nFinally, the paper states that providing information on computer resources for experiments is \"unnecessary\" because the experiments are \"small-scale.\" However, for better reproducibility and transparency, it is good practice to include basic details about the computing environment (e.g., CPU type, RAM) and typical execution times, even for small experiments.", "was_revised": true, "final_justification": "The authors satisfactorily addressed all of my questions. My rating remains unchanged.", "rebuttal": "**Can you discuss your assumptions further?**\nYes, we would be happy to provide a deeper explanation.\n\nIn 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.\nIn 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.\nThis makes the i.i.d. assumption a reasonable approximation.\nFor example, Airbnb, one of our motivating applications, has over 5 million hosts (i.e., suppliers) as of March 2025.\nOn the other hand, small-scale platforms may violate the assumption as the same participants may return frequently, and the population may shift over time.\nTherefore, if the focus is on established platforms, the i.i.d. model is appropriate.\n\nFor 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.\n\nRegarding Assumption 1.3 (Lipschitz supplier cost cdf), this condition ensures that the cost of supplying a good varies gradually across suppliers, rather than abruptly.\nIn other words, there are no large clusters of suppliers with costs concentrated in a narrow price range.\nThis is a natural assumption guaranteeing that small changes in the trading price lead to stable changes in the likelihood of the trade.\nAs 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.\nIn 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.\nAs 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.\nWe would argue that these types of scenarios with highly concentrated distributions are not overly common in practice.\nThus, the assumption of Lipschitzness is well-justified in most real-world scenarios.\n\nAssumption 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.\nIntuitively, the highest possible price is too high to justify any purchase by a retailer, resulting in zero net gain.\nFor 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. \nIf 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. \nThis behavior corresponds to a capped utility function, which is a common family of retailer utility functions where utility is zero beyond a certain price. \nOne 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.\nFollowing 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.\nThat being said, such cases typically require a pure monopoly over a market or an emergency setting, which are relatively rare.\n\n**In an i.i.d. setting, the incentive-compatibility proved in Theorem 2.1 is not that surprising.** \nWe will clarify what follows in the revised version.\nNote 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. \nThis is due to how the mechanism operates more than how the valuations of the participants are generated.\n\n**Add error bar and statistical significance.**\nThank 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. \n\nUnfortunately, 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):\n\n| Iteration | Mean Regret | 95% CI |\n|---:|---:|---:|\n| 100,000 | 3,041 | ± 19 |\n| 200,000 | 4,871 | ± 31 |\n| 300,000 | 6,271 | ± 43 |\n| 400,000 | 7,431 | ± 59 |\n| 500,000 | 8,434 | ± 70 |\n| 600,000 | 9,321 | ± 84 |\n| 700,000 | 10,133 | ± 98 |\n\n\nTo 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.\n\n**Add info about your computing environment and execution times.**\nWe 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.\n\n**How might changing the mediator's objective function affect the learnability, regret bounds, or even the mechanism design properties?**\nGreat question! The short answer is that those properties will vary depending on the objective.\nConsider the following three examples to illustrate some possible variations.\n\n1.  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$ }.\n\n2. 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$ }.\n\n3. 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$ }.\n\nRegarding learnability/regret bounds:\n\n- In the first two examples, the learner has access to bandit feedback. \nHence, 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).\n\n- 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.\n\nRegarding the mechanism-design properties:\n\n- 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.\n\n- In the second example, a proof like the one in Theorem 2.1 shows that incentive-compatibility and individual rationality are preserved.\nHowever, 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).\n\nWe are happy to add these future directions to Section 7 in the revised version of this work.\n\n---\n\nWe hope our answers helped clarify all lingering doubts. \n\nIf this is the case, we'd kindly ask the reviewer if they would consider readjusting their score."}, {"review_id": "4KhiIpHEw9", "reviewer": "Reviewer_QQVf", "summary": "The paper studies a repeated mediated newsvendor problem (RMNP) where the learner is a mediator that facilitates trades between suppliers and retailers in a sequence of interactions. It proposes an online mediator’s pricing strategy that achieves the optimal regret rate with theoretical guarantees and experimental validation.", "questions": "1. While the paper assumes retailer utility functions belong to the class of upper semi-continuous (USC) functions, is this assumption common in prior newsvendor literature?\n\n2. Does the model account for the overage cost of unsold goods. If not, how does this cost impact the derived regret bounds?", "limitations": "Overall, the paper does not show significant limitations. Some minor limitations include:\n\n1. The experimental section lacks error bars and repeated trials, which hinders the evaluation of algorithm stability under stochastic variations.\n\n2. The theoretical framework relies on idealized assumptions, which may not hold in real-world supply chains with non-stationary dynamics or concentrated cost distributions. Such gaps could limit the model’s applicability.", "rating": 4, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "**Strengths:**\n\n**Strong theoretical contributions:** The derived regret bound is tight and matches the lower bounds up to some logarithmic factors. The authors also verify the necessity of all assumptions involved in the study.\n\n**Clear structure:** This paper is well-organized with intuitive proof sketches.\n\n**Weaknesses:**\n\nThe paper's theoretical assumptions exhibit notable gaps in aligning with real-world supply chain dynamics, particularly regarding Assumption 1.1 (i.i.d. sequences). While the proof of assumption necessity in Appendix E constructs counterexamples to show linear regret, it overlooks weaker relaxations that better model practical scenarios. For example, adaptive algorithms might still achieve sublinear regret in mildly dependent processes (e.g., ARIMA-simulated time-series with seasonal trends), where temporal correlations are weak but non-negligible.\n\nIn the experiment part, the study omits repeated trials across diverse supplier cost distributions and retailer utility functions, failing to report error bars or confidence intervals for regret. This absence prevents robust assessment of the algorithm’s stability under stochastic fluctuations.", "was_revised": true, "final_justification": "The authors have added repeated experiments and included error bars, which improve the completeness of the results. However, the model still relies on somewhat strong assumptions, which limit its practicality and broader applicability. Therefore, despite these improvements, I have decided to keep my original score.", "rebuttal": "**Is the USC assumption common?**\nGood question. As far as we know, it is not a common assumption. \nTo the best of our knowledge, the most common assumption by far is that utilities are (at least) Lipschitz. \nOur USC assumption is weaker (in fact, even strictly weaker than continuity alone) but still sufficient for our theory.\nIn particular, all (possibly discontinuous) right-continuous non-decreasing functions are upper semi-continuous and can therefore be encompassed by our theory.\nWe will highlight this in the revised version.\n\n**Does the model account for the average cost of unsold goods? If not, how does this cost impact the derived regret bounds?**\nIn our setting, goods are produced only after they are ordered.\nFor 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.\nSimilarly, 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.\nHowever, this is an interesting direction to explore for future work and we thank the reviewer for their suggestion.\n\n**Add error bars.**\nWe 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.\n\n**Are our assumptions realistic?**\nWe thank the reviewer for raising this point and are happy to clarify.\n\nAs shown in Theorem 5.1, if any one of the assumptions is relaxed, sublinear regret is no longer achievable.\nThus, 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.\n\n\nThat being said, an interesting direction for future work would be to explore relaxations of the problem setting. \nFor example, the weaker benchmark of $\\alpha$-regret may allow for learnability under non-stationary dynamics.\n\nWe also note that several real-world applications in which our assumptions are approximately satisfied are discussed in the motivations section.\nPlease 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.\n\n---\n\nWe hope our answers helped clarify all lingering doubts. \n\nIf this is the case, we'd kindly ask the reviewer if they would consider readjusting their score."}, {"review_id": "vYepOC6LLY", "reviewer": "Reviewer_LmM4", "summary": "This paper considers the problem of online learning with a mediator learning the behavior of the supplier and the buyer. Specifically, the learner proposes a price $p_t$ at each round $t$, observes $1\\\\{p_t\\leq c_t\\\\}$ indicating whether the supplier accepts the trade and $U_t^{\\sharp}(p_t)$, indicating the amount the buyer will buy based on the buyer's utility function $U_t$. The goal is to maximize the total gain-from-trade. The author shows that this is a strict generalization of online bilateral trading problem, a problem setting that is well motivated and recently studied broadly.\n\nUnder the assumptions that $c_t$ and $U_t$ are independent and stochastic, the authors first provide a UCB-based algorithm achieving $\\tilde{O}(T^{2/3})$ regret, together with a nearly matching lower bound. The algorithm works on the discretized price set and is split into two phases. The first phase is a pure exploration phase, which aims to provide a UCB estimate for $\\mathbb{E}[(p-c)^+]$ and $\\mathbb{E}[U^*(p)]$ that is fixed in later rounds. The second phase then uses the previously obtained UCB estimates and further applies a UCB based algorithm based on the estimated gain-from-trade for each discretized price. The authors also show that all the assumptions they made are necessary in the sense that if one of these assumptions does not hold, there is no algorithm that can achieve sublinear regret. This is proven by reducing this problem to online bilateral trading. The authors also conduct experiments to verify their theoretical findings.", "questions": "I have some questions about the derivations:\n- Assumption 1.3 is not well-defined. What is the Lipschitz constant that is assumed for the CDF for $C$?\n- In Line 895, can the authors explain more about how they use Assumption 1.3? It seems that the definition of $m$ is missing.\n- As for the UCB estimates in the first phase, I wonder whethere there are some intuitions that the confidence interval is $O(1/K)$ for **each** price $p$ given only $K$ samples for that price? My (vague) intuition is that the UCB estimates for smaller $p$ requires less samples to approximate and for larger prices, they can utilize the observations from smaller prices since the estimate is based on CDF but I am not clear about this. Can the authors explain more about this?\n- Also, can the authors comment more about how more relaxed feedbacks could potentially improve the regret rate?", "limitations": "Yes.", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 4, "clarity": 2, "significance": 3, "originality": 4, "strengths_and_weaknesses": "Strengths:\n- The problem is well-motivated and is a generalization of the online bilateral trading problem.\n- The authors provide an almost optimal upper and lower bound for this problem under the assumptions they made. Moreover, the authors show that the assumptions are necessary to achieve sublinear regret for this problem.\n- I checked the proofs and they look correct in general, except for some parts that I will point out in later sections.\n- The author also provide empirical evidence to show the effectiveness of their algorithm, together with the justifications on the assumptions they made.\n\nWeakness: I do not find major issues for this paper but I think the derivations in this paper can be further polished.\n- The Lipschitz constant is not defined in Assumption 1.3.\n- The explanation of the confidence interval \\mathcal{E}_{\\psi,\\delta,j} and \\mathcal{E}_{\\phi,\\delta,j} is missing. Specifically, I am not sure whether $U_{k,i}^{\\sharp}(p)$ (shown in line 903) is defined. In addition, there are some inconsistancy in the proof. For example, in line 903, $\\mathcal{E}_{\\phi,\\delta,j}$ is defined with respect to $\\frac{1}{K(K-j)}$ and in line 924, it changes to $\\frac{1}{K^2}$. While I understand the high-level intuition of the proof and most of the results are as expected, I do not understand some detailed derivations (see questions) and I wonder whether the authors can explain more in detail.", "was_revised": true, "final_justification": "Based on the rebuttal and other reviewers' review, I keep my original rating of this paper.", "rebuttal": "**Is $U^{\\sharp}_{k,i}(p)$ defined?**\nWe 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). \nBut 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. \nWe implemented this change for the revised version.\n\n**Typos on line 903.** \nThank you for catching it!\nThe 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. \nWe double-checked and didn't find any other occurrences of these typos. We updated the revised version with this change.\n\n**Assumption 1.3 has a missing \"$m$\".**\nThank you for catching this typo as well!\nAssumption 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\n$\\mathbb E [ \\mathbb I$ { $p_j < C \\le p$ } $]=\\mathbb P [ p_j < C \\le p ] \\le m \\cdot (p - p_j)$.\nWe updated the revised version with this change.\n\n**Why few samples give $O(1/K)$-sized confidence intervals.**\nThe reviewer's intuition is roughly correct.\nFor 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$. \nAs 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]$).\nThe 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.\n\nAs 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$).\n\n**Could the authors comment more about how more relaxed feedback models could potentially improve the regret rate?**\nIntriguing question.\nA feedback of theoretical interest that is commonly considered is \"full feedback\".\nIn our setting, this would mean that $C_t$ and $U_t$ are revealed at the end of each round. \nWe make the following conjectures for this setting: \n1) Independence of $C_t$ and $U_t$ is not necessary to guarantee learnability, and neither is Lipschitnzess of the cdf of $C_t$; \n2) 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.\n\n---\n\nWe hope our answers helped clarify all lingering doubts. \n\nIf this is the case, we'd kindly ask the reviewer if they would consider readjusting their score."}]

Author rebuttal:

Meta-review: This paper studies an online learning version of the repeated mediated newsvendor problem. On the upside, 
- the reviewers acknowledge that the paper provides substantial theoretical results
- in the rebuttal, explanations of the assumptions, the construction of confidence bounds for gain-from-trade, and the necessity of pure exploration, detailed experimental results were all deemed useful 

On the downside, the reviewers think that:
- the work still relies on somewhat strong modeling assumptions, which limit its practicality and broader applicability.
- the novelty may be moderate, given that the paper builds closely on prior bilateral trade literature

Given these considerations, this paper is at the borderline of acceptance.
Decision: Accept (poster)