Feature-Based Online Bilateral Trade
Authors: Solenne Gaucher
Martino Bernasconi
Matteo Castiglioni
Andrea Celli
Vianney Perchet
Venue: ICLR 2025 Poster (2025)
Keywords: bilateral trade
online learning
contextual bandits
Primary area: reinforcement learning

Abstract: Bilateral trade models the problem of facilitating trades between a seller and a buyer having private valuations for the item being sold. In the online version of the problem, the learner faces a new seller and buyer at each time step, and has to post a price for each of the two parties without any knowledge of their valuations. We consider a scenario where, at each time step, before posting prices the learner observes a context vector containing information about the features of the item for sale. The valuations of both the seller and the buyer follow an unknown linear function of the context. In this setting, the learner could leverage previous transactions in an attempt to estimate private valuations. We characterize the regret regimes of different settings, taking as a baseline the best context-dependent prices in hindsight. First, in the setting in which the learner has two-bit feedback and strong budget balance constraints, we propose an algorithm with $O(\log T)$ regret. Then, we study the same set-up with noisy valuations, providing a tight $\widetilde O(T^{2/3})$ regret upper bound. Finally, we show that loosening budget balance constraints allows the learner to operate under more restrictive feedback. Specifically, we show how to address the one-bit, global budget balance setting through a reduction from the two-bit, strong budget balance setup. This established a fundamental trade-off between the quality of the feedback and the strictness of the budget constraints.

Published as a conference paper at ICLR 2025
REATURE-BASED ONLINE BILATERAL TRADE
Solenne Gaucher'
Martino Bernasconi
Matteo Castiglioni
Andrea Celli?
Vianney Perchet
CMAP, École polytechnique, IPP Bocconi University
3 Politecnico di Milano Criteo Al Lab 5 Fairplay team, CREST, ENSAE, IPP
{mart i no. bernasconi, andrea. cwwlieeellle.e..e cew matteo. castigl peetigllion onn 2pol i it, vianney wwwpeetereerrreeee eespp... solenne,
ABSTRACT
Bilateral trade models the problem of facilitating trades between seller and a buyer having private valuations for the item being sold. the online version of the problem, the learner faces a new seller and buyer at each time step, and has to post a price for each of the two parties without any knowledge of their valua- tions. We consider scenario where, at each time step, before posting prices the learner observes a context vector containing information about the features of the item for sale. The valuations of both the seller and the buyer follow unknown linear function of the context. In this setting, the learner could leverage previous transactions in attempt estimate private valuations. We characterize the re- gret regimes of different settings, taking as a baseline the best context-dependent prices in hindsight. First, in the setting in which the learner has two-bit feedback and strong budget balance constraints, we propose an algorithm with Ollog T') regret. Then, we study the same set-up with noisy valuations, providing a tight OTT//s regret upper bound. Finally, we show that loosening budget balance con- straints allows the learner to operate under more restrictive feedback. Specifically, we show how to address the one-bit, global budget balance setting through re- duction from the two-bit, strong budget balance setup. This established fun- damental trade-off between the quality of the feedback and the strictness of the budget constraints.
INTRODUCTION
Bilateral trade models scenarios which a seller and buyer, both having a private valuation for good, interested in trading it in order to maximize their respective utilities (Vickrey) 1961 Myerson & Satterthwaite 1983). We study the online bilateral trade problem introduced by Cesa- Bianchi al. (2021). At each time t, new seller and buyer arrive, with private valuations 8, and bt respectively. The seller's valuation 8, is the lowest price they are willing to accept for the item. Analogously, the buyer's valuation d, represents the highest price they are willing pay for the item. The learner, without any knowledge about the private valuations at the current time i, posts two (possibly randomized) prices: pt the seller and q, to the buyer. A trade happens when 8, pt and q < by, so both agents agree to trade. The gain from trade (GFT) for pair of prices (p. q) at time is
GFT, q) 1(5, S p}1la S be) st).
(I)
This represents the net utility gain generated by the trade. Following online bilateral trade litera- ture (see, e,g., Cesa-Bianchi al. (2021) 2023): Bernasconi et al. (2024). we assume the learner aims to maximize trade gain or equivalently minimize regret relative to the best hindsight policy! !! A key challenge in online bilateral trade is the inherently limited feedback: under two-bit feedback, the learner receives feedback (T({x; & pt) The 2 qe )). and under one-bit feedback the learner only observes whether the trade occurred, that is T (& E pt) T(b, 2 g.). Both provide far less informa-
We note that gain from trade and social welfare (i.e, the sum of the utilities of both agents if the trade occurs, the seller's utility if it does not) result in the same notion of regret

---

Published as a conference paper at ICLR 2025
tion than traditional bandit feedback, since the learner cannot even reconstruct the gain from trade received for the prices it posted.
In the standard model of bilateral trade, the platform lacks information about the seller, buyer, the item being sold. However, this scenario is unrealistic in practice, where some information is usually available to the learner. In contexts like online marketplaces, where products often differentiated, the learner can observe product features upfront and base pricing decisions on them, using past trade data to estimate feature values and inform future pricing.
We introduce the feature-based online bilateral trade problem, in which the learner observes a fea- ture vector 3t E IRd before posting prices for round 1. Building on the traditional feature-based dynamic pricing framework (see. e.g., Cohen et al. (2020); Javanmard (2017); Javanmard & Naz- erzadch (2019); Keskin & Zeevi ; & Wang (202T) ) we study the setting in which private valuations are of the form 2; 0 Et, where A E IR" is an unknown vector denoting the importance of each feature, and & is an i.i.d. noise term. Following the set-up of Cohen et al. (2020), feature vectors 2e are chosen adversarially by nature. This ensures that our solution is robust to scenarios where features are correlated and where the set of relevant features evolves over time.
1.1 OUR CONTRIBUTIONS
In this paper, we introduce the feature-based online bilateral trade model, and characterize the regret for various scenarios with adversarially generated feature vectors.
First, we focus on the scenario in which the learner has two-bit feedback and strong budget balance constraints (the learner has to set the same price to the seller and to the buyer, i.e., Pt qt at each round t). As preliminary warm-up, we begin by considering the deterministic setup where, at each f, the seller's valuation is s, z, 8" and the buyer's valuation is b, x._ 8h. We show that in this case, it is possible to adapt techniques proposed by [Cohen et al. (2020) in the context of feature-based dynamic pricing. The main difference here is that we need to maintain separate ellipsoidal uncertainty sets for the seller and the buyer, respectively. Our analysis yields a regret of order (log T') (Proposition!!
Two-bit, noisy valuations. Then, consider the case of noisy valuations in which & = x 0 0 + E and be x 8h + Et, where şi and E are i.i.d. noise terms independent from It. with bounded support and densities. We start by decomposing the expected gain- gein-from-trade into components that can be individually estimated using two-bit feedback (Lemma I Then, we describe an explore- or-commit (EOC) algorithm with regret O(T%)) (Theorem 1) (this algorithm will be employed in the subsequent reduction to the one-bit setting). Finally, we devise a SCOUTING BANDITS WITH INFORMATION POOLING algorithm, which makes more efficient use of the information collected during the learning phase. This algorithms achieves a regret (Theoremm 2). which is minimax optimal up to poly-logari factors and dependence d. Indeed, there exists a matching S(TT lower bound for the stochastic bilateral trade problem without features in the case of independent valuations with bounded densities and support Cesa-Bianchi et al. (2021).
One-bit reduction. Finally, we provide a general black-box reduction that demonstrates how the difficulty of maintaining a per-round budget balance can be traded for the ability to operate under more demanding feedback conditions. In particular, given two-bit explore-or-comme guaranteeing strong budget balance and sublinear regret, we show that it is possible to construct a no-regret algorithm that works under one-bit feedback, and is global budget balanced (Theorem 3 The one-bit regret guarantees are dependent on natural measure of the social welfare generated by the market.
algorithm
1.2 RELATED WORKS
Bilateral trade. In the offline setting, Myerson & Satterthwaite (1883) showed the existence of
instances where a fully efficient mechanism that satisfies incentive compatibility, individual ratio- nality, and budget balance does not exist. Subsequent research focused on finding approximately
efficient mechanisms in the Bayesian setting Blumrosen & Dobzinskil (2014); Kang et al. 2022);
McAfee (2008): Blumrosen & Mizrahi (2016); Brustle et (017) Deng et al. (2022 Fei 2022
2

---

Published as a conference paper at ICLR 2025
Online bilateral trade. Cesa-Bianchi et al. Cesa- Bianchi et al. (2021); y; Desa-Bianchi et al. (2024) study the case in which valuations are drawn i.idd from some fixed unknown distribution and the learner has to enforce strong budget balance. They provide sublinear regret guarantees in the full- feedback setting, and under partial feedback when valuations are i.i.d. samples from a smooth dis- tribution, independently for the seller and the buyer. If the learner is only required to enforce weak budget balance (i.e., S for each t), then Azar et al. (2022) provide an algorithm achieving tight sublinear 2-regret when the sequence of valuation is generated by an oblivious adversary. Cesa- BiiacBi et al. (2023) show that sublinear regret can be achieved beyond the i.i.d. stochastic setting under a o-smooth adversary model. [Bernasconi et al. (2024) show that sublinear regret can be achieved in the fully adversarial setting if the learner enforces global budget balance constraints (i.e., the constraint has to hold over the entire time horizon). related setting to online bilateral trade is online brokerage (Bolić et al. (024). This model has some key structural differences from the standard online bilateral trade framework by [Cea- Sesa-Bianchi et al. (2021). For instance, traders market conditions, and their valuations
can act as both buyers and sellers depending from the same unknown distribution. |Bachoc et al. (2024) recently studied a contextual brokerage model where traders' valuations are zero-mean perturbations of market price that is linear in the feature vector.
i.id.
Feature-based pricing. The one-dimensional version of the problem was introduced by Klein- berg & Leighton| (2003), while et al., (2014) introduced the problem in the contextual, multi- dimensional set-up under i.i.d. contexts. Cohen et al. (2020) study a model with adversarial contexts for which they provide O log T)) regret guarantees in the noiseless setting, improving over the Õ(VT) guarantees obtainable with general-purpose contextual bandits algorithms Agaawal et al. 2014). Moreover, they provide O(T4/s regret guarantees for scenarios with adversarial contexts and additive noise generated from a known sub-Gaussian distribution. Further improvements in the achievable rates were later provided by [Lobel et al. (2018): Leme Schneider (20T8); [Liu et al. (022). Further instantiations of the feature-based pricing model can be found in the survey of Den Boer (0115).
PRELIMINARIES
For any l 2 1, we compactly denote the set f1,2...., John ellipsoid of a convex body H (i.e., the minimal volume ellipsoid that contains Hf) For a positive definite matrix M E dddd and E Rd, we denote Vx Mr by || In our proof sketches, write Ar & Br if there exists a problem-dependent constant c such that Ar cBr.
k} as [k:]. We denote by LJ(H) the Löwner-
Learning protocol. At each round t, a new buyer and a seller arrive, characterized by private valuations b, and st, respectively. After observing feature vector 2, Rd. the learner posts two prices: Pt to the seller and qe to the buyer. The trade happens if both agents accept the proposed prices, that is 8, S Pt and qe S by- When the trade happens the learner is awarded the gain from trade GFT,(Pt, gt), defined as per Equation adversary.
Feature vectors 24 are generated by an oblivious
Valuations. We consider two models to describe how features impact the seller's and buyer's valuations. In the first setting, valuations are a deterministic function of the context. At each round t e [T]. the valuations of the seller and of the buyer are given by
8t = = 0 and
b. x==x] 0².
respectively, where 8* 0² E d are unknown to the learner. We assume that both the contexts di and the parameters I and lr bounded.
Assumption 1. There exist A, B 2 0 such that max([101]1. [[0*1) s A, and | fl < B.
In the second setting, we consider noisy valuations. At each round t E [7]. the valuations are given by
b. = xx. 0² ct and 8, =; x 6" E;
where ? and & are i...d centered noise terms independent from the context 24, with densities fh and fs, respectively. We denote by F the c.d.f. of E², and by De the demand function of eh for all R, (x)) = IP (sf æ). We make the following assumption the densities of & and st
3

---

Published as a conference paper at ICLR 2025
Algorithm ELLIPSOID FOR BILATERAL TRADE (EP-BT)
Input parameter 0, bound A.
2: Initialize KJ, K + d-dimensional ball of radius A, Ej = LJ(K)) and E L)(K))
3: for E [ do
4: Set St E; z and 5t = ma xz and compute (be, bt) analogously
5: if 8, < b then post price Pt (st b,)/2
6:
else if' 5.
2 then
7:
Post price pt = (5r + 52
8:
Update Ki+1 according to the seller's feedback, set Ej+1 LJ(K+t)
9:
else if b; be 2 then
Post price pt = (b, + b2)/2
11:
Update K2+1 according to the seller's feedback, set E LJ(K
12:
else post price pt (s: b2
Assumption 2. Both çi and E are supported in |-C, C)2 and have densities bounded by L.
We observe that under Assumption 1 and the valuations of the seller and the buyer are bounded in [-P, PI. where = C+ AB trade problems with stochastic valuations, and there exists linear regret lower bounds for the case in which this assumption is lifted (Cesa-Biancee et al., 2024).
p The bounded densities assumption is standard in repeated bilateral
Feedback models. After posting prices (Pr. qt). the learner does not observe directly the GFT or the valuations, but receives some feedback about the transaction. We focus two feedback models: (i) Two-bit feedback, where both the buyer and the seller reveal their willingness to accept the prices offered by the learner (i.e., 2t composed by the bits (T{ss p.): Tfq S b)))); ) (ii) One-bit feedback: the learner only observes whether the trade happened or not (i.e., 2t = Tf I pc] lgg, S ).. Both feedback models have the desirable property of revealing minimal information about agent's 's private valuations.
Regret. Our objective is to develop dynamic policies that perform well in terms of minimizing regret. In the deterministic setting, the worst-case regret for learning algorithm is defined
(A) = (0" -*)
max
Σ (IxT (0 0*)]* GFTeepp, q))) (E[T]
In the noisy model, we compare against benchmark that maximizes the expected gain from trade. Let EGFT(Z.,.0g E (GFT.((P.))) x; = z). The pseudo-regret for the noisy setting defined as
(r( = Σ max EGF (p..) p5a
Σ EGFT Pt,,
1El21
<ETT
A property that directly follows by definition is that, for any feature vector, there exists a pair of identical prices that maximize the expected gain from trade. To simplify the notation, omit the argument 9 of GFT, and EGFT the same price is posted to both agents.
WARM-UP: TWO-BIT FEEDBACK, STRONG BUDGET BALANCE, NO NOISE
In this section, we consider the simplest set-up in terms of the information available the learner, by focusing on the setting with two-bit feedback and deterministic valuations following Equation (2) We adapt the ELLIPSOID based dynamic pricing, to bilateral trade problem. The key distinction lies in managing separate uncertainty sets for the seller and the buyer, while carefully setting prices consistent with both esti- mations. In this set-up, main step of ELLIPSOIDPRICING FOR BILATERAL TRADE (EP-BT).
algorithm, originally proposed by Cohen et al. (2020) for feature-
update these uncertainty sets separately. Algorithm T describes the
Proposition 1, Assume that the seller's and buyer's valuations follow Equation 22. Under Assump- tion 7 Algorithm with = ABd2 /T has regret bounded by RT S 10ABd log (20(d + 1)Tdd?).
For simplicity, we work within ;- PP, P). If non-negative prices are required, translation suffices.

---

Published as a conference paper at ICLR 2025
Algorithm 2 ESTIMATION SUBROUTINES
1: procedure EST-PAR(7E<)
DUpdate estimate of parameters 0%,
2: Draw price Pt Ui-- PJ) and post (Pe.Pt)
3: V - EiEToo 2 +Ia
4: 0" + 2PV-PV11 LIETi (1(pr S 81)
5: 0 -2PV- SPVV-EIETO "EITTE (T(p <b)
6: procedure EST-INT(T
>Update estimate of integrals I, J
7: Draw price Pt. ~ U(| PP, Pl) and post (pt: Pt)
8:
for k E K. do
9:
j
2P
Eletn I S pi S kc + 2/ 0-
T
10:
7
EiETIO T he + xr S p 1 bi
1
11: procedure EST-F(TE grid point k E K.) Post price pt x; fr + ke. Then update F. ElETE 1ss1 S P
Update estimate of F
13: procedure EST-D(TH) grid point k E K)
>Update estimate of D
14: Post price pt x 8 kc. Then update D Eiery I {bi P1
We observe that the algorithm explores only whenever the estimations are not precise enough. In the proof (Appendix B), we show that this happens in at most Ollog 7) rounds.
4 NOISY VALUATIONS WITH TWO-BIT FEEDBACK
In this section, we consider bilateral trade with two-bit feedback and noisy valuations. We introduce key components that we exploit in the analysis, before integrating them into an explore-or-commit framework which ensures a regret (TT)) Finally, we show careful re-design of the last phase of the algorithm yields tight regret upper bound of (TT%)s)
We rely on the following decomposition lemma, which extends Lemma of Cesa-Bianchi et al. 2024 to contextual settings. The proof can be found in Appendix E.1
Lemma 1. Under Assumptions
7 and 2
the expected gain from trade for x at price is given by
EGFT(x,P) =
(4)
where 8 p= x. T0 = x; 8h T(6) J (u)dd and J(Ø) = S_c (u)ddu
Lemma D emphasizes that the expected gain from trade for price p depends on the pair of price increments (8*,8"), or equivalently, on the pair (8", Ad), where the difference in average valu- ations A, is defined as A, == x (@b 8²). This shows that items with the same A, have the same optimal seller's price increment 87 if p x.! t 8, maximizes EGFT( :), and if Tp (0--00 ing the optimal increment 5 for specific A, not sufficient to determine the optimal increment for a different A, (see Appendix FF). Thus. finding the optimal price increment across various A values might require us precise estimate the reward function over broad range of increments. This is notable departure from the non-contextual stochastic bilateral trade problem discussed in CCesa-Bianchi al. (2024), where precise estimation of the reward function around the optimal price suffices. Since accurately estimating functions such as F Dd, T, and J across wide range of arguments complicates the problem, the regret might be higher than the ((7%))) rate achieved in Bianchi et al. (2024). Surprisingly, we show that with careful coordination of the various still be attained.
(P--0) 0²) = x (0' 0*), then p' - + 8 maximizes EGFT( -). However, know-
estimation procedures, the optimal rate for the non-contextual

---

Published as a conference paper at ICLR 2025
Algorithm 3 EXPLOEE- COMMIT FOR BILATERAL TRADE (EOC-BT)
1: Input: parameter length of estimation phases T THD discretization enror confidence d.
2: Initialize: K = [2P/c] + 3, + --K, K] 7 pDt = =T = for all k E K, Ia-
3: while / < T do
4: if ||
ja then T <- 7 (1), EST-PAR(TTRM)
5: else if [T < Tim then Tim <- Tim U (t), EST-INT(T"
6: else if for some
K., |T T or (TR T then
7: if [T < TED then T Th. U (t), EST-F(TT k k)
8: else if [T TED then Th t Th U EST-D(TH, k)
9: else
DExploitation phase
A: (k) = [ke- - xt ( 03
1
Choose (ke, kt) arg (k Eo T D J and post price Pt = x 0= + KeE
11:
4.1 BUILDING BLOCKS: SUBROUTINES FOR LEARNING PARAMETERS
We first present the sub-routines estimate the parameters and 0 and the functions Fs, D', and J used in the EGFT decomposition of Lemma These sub-routines serve as the base compo- nents for the subsequent algorithms.
The first sub-routine, EST-PAR, estimates the parameters 0 and 0h. It uses the fact that, if Pt. ~ U(I-P, PJ), then 2P (Uipr= S $ - 1/2) is an unbiased estimate of x, 0" (similarly for 0b). Then,
rely classical results to estimate the parameters (see Lattimore & Szepesvári (2020) Chapter 19)). The second sub-routine, EST-INT, estimates the integrals ( and J()) over grid of price increments (ke k E K... The third and fourth sub-routines, EST-F and EST- D, provide estimates of the c.d.f. F and the demand function Dd at ke for a given increment level k E K., respectively.
4.2 EXPLORE- -R DR-COMMIT FRAMEWORK
First, we consider a natural Explore- Or- -o-Comitt (EOC) algorithm which uses each round either to compute estimates for the terms in Eguation 44. or to greedily play the empirical best action. This strategy described in Algorithm algorithm. Indeed, it resorts to the estimation subroutine EST-PAR (Line[) whenever the estimation not "good enough" and not only the first rounds. The other estimation subroutines are executed until a certain number of updates is reached. We show that the number of necessary exploration rounds is upper bounded by O(T%)4) This will be useful in section Section 5 to handle one-bit feedback. Finally, in Lines 10 and TT the algorithm selects the best price increments according to the current estimates (i.e., "commit" rounds), and posts price Pt build accordingly both agents. Theorem Theorem Tbounds the regret of EOC-BT. Its proof is postponed to Appendix C where we provide explicit bounds on T and C.
Our algorithm not standard Cettore-The-CCommee
[[gg(T) 1/4
Theorem 1. Set 6
8 (T(74 + 32Pc-1) === c cPP dog
1+ B2T + A) A)-
Time verifies
SP log(1/6) and FD
22
Then, under Assumptions
and Algorithm
RT < CT log
with probability at least 1- T when T 2 T, where T and Č are constants depending respectively on A, B, and C, and on A, B. C, and d.
Sketch of the proof. For some > 0 to be chosen later, let KC = I-P/e, P/e]. Using standard arguments Abbasi- Yadkori et al. (201 1 Carpentier et al. (2020),
show that Õ(c samples are sufficient for EST-PAR to ensure that, with high probability, for all t T the errors x (6"
0.)] and |x, (@b 0.)1 are smaller than c. When this happens, classical concentration arguments ensure that (c-)) samples sufficient for EST-INT estimate Tlke and ((ke) with precision

---

Published as a conference paper at ICLR 2025
Algorithm 4 SCOUTING BANDIT WITH INFORMATION POOLING (SBIP)
1: Input: parameter μ > 0, length of scouting phase T discretization size c. confidence > 0.
2: Initialize: 7 TT Ø, V Ia. K 2P/c + 3, = [-K, K1. č (12PL 7)c,
3: Nik. = Nb. = p = D* O for all E K. Let B N n + 12
4: while t S T do
5: if || > then
6: T 7 {t}. (ST-PAR(TRM))
7: else if [T < Timl then
8: Tim t 7 U (t), (ST-IN
9: else
Run Successive Elimination
for (k, E A: ((h,K) E EK3 13:K= :k= (2) 00: 87) + kc) c-1 do
UCB - P + Jo + 2P (3(Nk..) + 3((VK())
11:
LCB, k²) )+)+ + 7 F.. + Jr DK - - 2P (B(Nk:n) + +(NKK.
12:
K;= ((k, k3 A. (k, (a LCB((L,(')
14:
Choose (kig kt) E arg &/K min(Nk.e, NW oy and post price pt x. 03 hit
Observe feedback and update:
pl.. Nke pike + Ise Pc} and DY Nk. D + +Ibb, pt}
N +1
No. +1
16:
Nkv.a + Nka. +1 and NK. + NAA +1
uniformly for E K. By contrast, Ö( samples are necessary for EST-F and EST-F to estimate F* (KE) and (kke) with precision uniformly for l E K. Thus, with high probability, after Ö(KK]e rounds of exploration, the expected gain from trade for prices x, 0; + ke is estimated with precision O(e) uniformly for & E K. Now, Assumption 2 ensures that the reward function is Lipschitz-contimuuus, so the discretization error is also O(c). By choosing the estimation and discretization errors with the regret of the exploration phase, thereby obtaining a regret ((T%))
T 1/4, we balance
4.3 CLOSING THE GAP: SCOUTING BANDITS WITH INFORMATION POOLING
The O(T%) regret of the EOC strategy is mainly due to the cost of estimating the c.d.f. Fe and demand function D To bypass this costly estimation, an alternative approach is to first estimate 0b 8" and J, then run independent scouting bandit algorithms (as described (2224) for each (rounded) value of A, = x (Ø' - 0*). As shown in Appendix H this strategy also achieves O1T) regret. This regret rate is higher than the rate (TT%)) achieved in non-contextual stochastic bilateral trade. Surprisingly, by combining the strengths of both strategies, we achieve a regret of (+)%).. This reveals that the contextual stochastic bilateral trade problem is no more difficult, in terms of regret, than its non-contextual counterpart, although the comparison is against a stronger benchmark.
CCesa-Bianchi et al.
To achieve this optimal regret rate, we design a scouting bandit strategy with information pooling across different values of A,, presented in Algorithm Information pooling is related to cross- learning, developed for bandits with graph feedback Balseiro et al. (2019). particular, after having estimated x. 6*, xr, 0², 1 and J, we run a successive elimination algorithm for each value of A,- Then, to estimate the reward a price corresponding to increments 8" and 86, we use the feedback from rounds where these increments have been selected across all values of A..
Theorem 2. Under Assumptions
[ and
Algorithm 4 with e = (d& log ( =
((38 + 16P) (( +
(P doog 1+BTT
+ and Tint = SSP log(1/6) verifies
Rr S (TTo2
with probability at least - 1/T when T > Т, where T and Č are constants depending respectively on A, B, and C, and on A, B, C, and d.
7

---

Published as a conference paper at ICLR 2025
The regret rate of Algorithm 4 matches the lower bound (3) established by Cesa-Biande et al. (202)) for the simpler problem of non-contextual stochastic bilateral trade under similar assumptions (i.e., independent valuations with bounded densities and support). Thus, aside from the constant C, the dependence on the dimension d, and logarithmic factors, Algorithm aacoiveeeachheeess achieves minimax-optimal regret. We outline the proof of this result below, with the full formal proof as well as bounds on T
and C deferred to Appendix D
Sketch of the proof. Let r(z, == maxy EGFT(x,, EGFT p). and T = 1770). The regret is bounded by 2P + 2PTim + ENeTouTa r(r,, The elliptical potential Lemma (Carpentier et al., 2020) implies that Tear S de (log(T)){=-) so T + Tim S dc log(T)) By using concentration arguments and exploiting the Lipschitz continuity of the reward, we can show that, for all t & TPE U UTtH and (k, kk) E A., (k,kk, UCB, k')] is valid confi- dence interval for EGFT( xx. 8 + kc). Now, want to show that r(x,, S (VV/Ntt + v V/NN" + e). To prove this claim, we define (ki ki", E arg max(A.))) EGFT x, 0+ + ke). The Lipschitz-continiity of the reward ensures that the discretization error is of or- der O(c). Moreover, [LCB, kt), UCB, (Kie, k)] and [LCB,(kt k("), UCB,(k; k(") are confi- dence intervals for EGFT (Iee, Pt) and EGFT xr. 0= + kre), respectively, and LCB, ki²) S UCB kf) by Line
13 Then, it holds that EGFT( x, 8= + kīe) EGFT Pt) is of order UCB,(ks, k.) LLBB, Kr, k)) + UCB, (kr, k.*) - [kB k((). Our choice of (ki,, ky) ensures that min N < min(N*i is NN "} (Line 14). Then, by definition of UCB and LCB, and since the discretization is at most O(e), we get r(ze. Pt) S (VT/N* + V1/NA, +c).
To bound the regret of the Successive Elimination phase, we consider separately the rounds (indexed by Tx) where the bound is dominated by V and ke where is dominated by V1/Na'' and K2 = k. Then, we decompose the regret of this phase EieTHUTu r Pt) E CreTT (() + EIETY Pe)), Choosing Ta 2- and ra x e, we consider the decreasing sequence of intervals (ra)asa- The previous result implies that if & e 10(1/)), 0(1/1++)) (/1/2++)),, ) then (Zt,Pt) S ra. Thus,
and the rounds (indexed by T
Σ r(o,, pi) $ 1
Σ
Ta (ra+1 - -2a) + ra|TT
ri
ISasa-1
This sum is of order log//// We sum over (k: k') E K, and use the fact that EtEK T T T while [C] = e- to conclude that Rr 0(1%))
TRADING OFF BUDGET BALANCE CONSTRAINTS FOR FEEDBACK
In this section, we show that it is possible to relax the budget balance constraints in order to handle scenarios with limited feedback. In particular, we show that any EOC-like algorithm for two-bit feedback (for instance, Algorithms and 33 can be suitably adapted to handle settings with one-bit feedback. To achieve this, resort to the notion of global budget balance recently introduced by Bernasconi et al. (2024) and we show that budget can be exploited to compensate for the lack of feed- back. The notion of global budget balance requires the learner to be budget balanced only "overall" (i.e., over the whole time horizon). In particular, let PROFIT, (p, 9) == Ii& & p) I b2 p) be the profit extracted by the learner at time by posting prices (p. q). Then, the learning algorithm
global budget balanced if the following inequality holds: Σ PROFI 4:) 2 0.
Given an EOC-like algorithm for the two-bit strong budget balance set-up, the idea is to simulate its exploration rounds by doing separate updates for the seller and the buyer, each using a single bit of feedback. In particular, each time in which the two-bit algorithm uses the seller's feedback Ifs; I p). the one-bit algorithm needs to actively collect that information by posting (P) in- stead of (p, p). Notice that, even under one-bit feedback, if the learner posts price (p. -P) it is able to observe 1[s,, < p} since the buyer is always going to accept the trade. Analogously, when the two-bit algorithm would employ T(b, 2 p), the one-bit algorithm has to collect that information by
8

---

Published as a conference paper at ICLR 2025
posting p). For instance, instead of executing EST-PAR, the one-bit algorithm runs two explo- ration phases: one in which updates only 0* (f EST-PAR) by posting (pr. -P), and one in which it updates only @ by posting (P. pe). The same happens for the other estimation subroutines.
The one-bit algorithm simulates finer-grained feedback by posting pairs of prices (P.p). (p. PP), resulting in negative GFT. By enforcing global budget balance, we allow the learning algorithm to set prices that not budget balanced individually, as long the overall budget balance is main- tained. To do that, we add an initial "budget-collection" phase, allowing the algorithm to accumulate enough profit for subsequent exploration rounds. In the following, profit can be accumulated during the budget-collection phase without incurring excessive regret rela- tive to GFT. This allows to provide sublinear regret guarantees under one-bi, feedback, with rates depending some natural characteristics of the underlying market. This approach is specifically suited for FOC-like algorithms, which require a limited number of learning rounds before starting to set greedy prices without requiring further feedback. By contrast, algorithms such Algorithm rely on two-bit feedback in each round to continuously refine their estimates of and F. Accumu- lating sufficient budget to emulate two-bit feedback throughout the entire time horizon would yield linear regret, rendering the reduction scheme inapplicable.
demonstrate how sufficient
Collecting budget. Let B be the budget required by the one-bit algorithm to cover the rounds in which it must post either (P) (p, PP) to collect information (the value of B will be set later). Therefore, the budget collection phase ends as soon as Σ, PROFIT (Pe, 9e) 2 B. We denote by r the random variable indicating the last round of the budget-collection phase. Moreover, let T == [r] be the random set of rounds designated for budget collection. For each round t T the algorithm samples a price uniformly from [- P), and a value i, uniformly from [0, log Then, it posts pair of prices (Pt, qt), where qt Pt + 2 We start by providing lower bound to the per-round expected profit obtained this way.
Lemma 2.
For each round t E T such that b, 2 st, it holds: E|PROHI,, 90] 2
(b.-s.)² 2 8P log T
where the expectation is with respect to the choice of (p.,
Our guarantees for the one-bit feedback case will depend on instance-dependent properties of the market. We measure this by looking the per-round GFT that be extracted on sufficiently long windows of time.
Definition 1. Given a sequence of valuations {(E,, bx) bt) a is defined as
bb. - st]
:=
min 2'2log
1'
rEle))
Intuitively, a measures how easily the learner can accumulate budget. The budget-collection phase will have at least length of order log T since T 2 8/2P, and B 22og T') even in the setting without noise. Then, we can show that the profit accumulated by time - is at least a factor of 1/ log T of the cumulative GFT up that point, assuming all trades up r had occurred
Lemma 3. For T 2 log T, it holds with probability at least 1/T that
(RO rE[r]
Σ
[b. xE|r]
Σ
s,]+
4P log(T)
Σ bb s,]+ 2. rE[r]
8Plog(T) (T)
Now let A be a two-bit algorithm such that, with probability at least 1 - 1/T, it requires at most TE exploration rounds, and has regret for the commit phase of R2f bit). We set the overall budget to be collected to
B max 22048P*a log T, 2PT
(5)
The first argument is used in the following proof to establish an upper bound on concentration terms, while the second accounts for the exploration costs over E rounds. Then, the resulting one-bit learning algorithm has the following guarantees.
With probability most 1 I/T, the budget B may be insufficient for 7 exploration rounds. In this case, halt exploration and begin posting arbitrary strong budget-balanced prices.

---

Published as a conference paper at ICLR 2025
Theorem 3. Given the two-bit algorithm A, the corresponding one-bit learning algoritlum satisfies global budget balance and, with probability at least 1/T. has regret
R4 bit) < < (a 3 log T) + R2
The guarantees above rely on the specific characteristics of the market, represented by the parameter a. When (11) the market is well-behaved, meaning that trade opportunities arise frequently enough. This occurs, for example, when buyers are willing to pay more than the seller's asking price, if only by a small margin. When leveraged. For instance, under the set-up of Section we can use Algorithm 3 as the two-bid algorithm A. Then, B < 4PT = 4P- APP.2P((T5) ( pur +T +2| ) which is of order Ö(P4 O(P*dT"/') /1" Therefore, the final regret bound in the noisy, one-bit setting with global budget balance is of order O(T%/4). A similar argument shows that in the noiseless setting of Section 3 the regret is order polylog(T).
[2(1), the guarantees of Theorem can be effectively
When the market is not well-hehaved, we can still establish sublinear regret guarantees under one-bit feedback and global budget balance. Indeed, through steps analogous to those of Lemma 3 show that
we can
EmEr1 PROFIT-((e... q:) 2 0 (F
+:)1+) (0)) -Ö(TT)
-
Moreover, exploit the fact that we can decompose the one-bit regret
R( bit) s Eee lb. st]* + (og(T))log(T) 27 + R( (see proof of Theorem 3
Then, if we take the budget B (or, equivalently, T) to be log T. the expression above yields T (i.e., the market does not
E. - sz]t /2T//4) In the worst case have allow to collect enough budget), which yields regret of order O(T%/4) in the deterministic set-up of Section 3 By setting B ~ 7 we achieve a regret of (TT% in the noisy set-up of Section Clearly, the rates are worse compared to the case where a 2(11, due to the difficulty in accumu- lating sufficient budget to cover the cost of posting non-budgee non-budget balanced prices.
ACKNOWLEDGMENTS
MB and MC are partially supported by the FAIR (Future Artificial Intelligence Research) project PE0000013, funded by the NextGenerationEU program within the PNRR-PE-AI scheme (M4C2, investment 1.3, line on Artificial Intelligence). MC is also partially supported by the EU Horizon project ELIAS (European Lighthouse of AI for Sustainability, No. 101 101120)37). AC is partially supported by ERC grant (Project 101 165666 the French National Research Agency (ANR) under grant number ANR-19-CE22 0026 as well as from the grant "Investissements Avenir" (LabEx Ecodec/ANR Saaeec/AAR----LLBXX 11-LABX-0047),, SG gratefully acknowledges funding from the Jacques Hadamard Foundation (FMJH).
STERR. VP acknowledges support from
Funded by the European Union. Views and opinions expressed are however those of the author(s) only and do not necessarily reflect those of the European Union the European Research Council Executive Agency. Neither the European Union nor the granting authority can be held responsible for them.
REFERENCES
Yasin Abbasi-Yadkott Dávid Pál, and Csaba Szepesvári. Improved algorithms for linear stochastic bandits. In Advances in Neural Information Processing Systems, volume 24, 2011.
Alckh Agarwal, Daniel Hsu, Satyen Kale, John Langford, Lihong Li, and Robert Schapire. Taming the monster: A fast and simple algorithm for contextual bandits. In International Conference Machine Learning, pp. 1638-1646. PMLR, 2014.
Kareem Amin, Afshin Rostamizadeh, and Umar Syed. Repeated contextual auctions with strategic buyers. Advances Neural Information Processing Systems, 27, 2014.
10

---

Published as a conference paper at ICLR 2025
Yossi Azar, Amos Fiat, and Federico Fusco. An a-tegret analysis of adversarial bilateral trade. In Advances in Neural Information Processing Systems, 2022.
François Bachoc, Tommaso Cesari, and Roberto Colomboni. A contextual online learning theory of brokerage. arXiv preprint arXiv:2407.01566, 2024.
Santiago Balseiro, Negin Golrezaei, Mohammad Mahdian, Vahab Mirrokni, and Jon Schneider. Contextual bandits with cross-learning. Advances in Neural Information Processing Systems, 32, 2019.
Martino Bernasconi, Matteo Castiglioni, Andrea Celli, and Federico Fusco. No-regret learning in bilateral trade via global budget balance. In Proceedings of the 56th Anmual ACM Symposium on Theory of Computing, pp. 247-258, 2024.
Liad Blumrosen and Shahar Dobzinski. Reallocation mechanisms. In Proceedings of the ACM Conference on Economics and Computation, pp. 617. ACM, 2014.
Liad Blumrosen and Yehonatan Mizrahi. Approximating gains-from-tradde in bilateral trading. In WINE, volume 10123 of Lecture Notes in Computer Science, pp. 400-413. Springer, 2016.
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, pp. 224, 2024.
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, pp. 589-590, 2017.
Alexandra Carpentier, Claire Vernade, and Yasin Abbasi- The elliptical potential lemma revisited. arXiv preprint arXiv:2010. 2020.
Nicolò Bisa-Bianchi, Tommaso Cesari, Roberto Colomboni, Federico Fusco, and Stefano Leonardi. A regret analysis of bilateral trade. In Proceedings of the ACM Conference on Economics and Computation, pp. 289-309, ACM, 2021.
Nicolò Desa-Bianchi, Tommaso Cesari, Roberto Colomboni, Federico Fusco, and Stefano Leonardi. Repeated bilateral trade against smoothed adversary. In COLT, volume 195 of Proceedings of Machine Learning Research, pp. 1095-125 130. PMLR, 2023.
Nicolò Cesa- Bianch,, Tommaso Cesari, Roberto Colomboni, Federico Fusco, and Stefano Leonardi. Bilateral trade: regret minimization perspective. Mathematics of Operations Research, 49(1): 171-203, 2024.
Maxime C Cohen, Ilan Lobel, and Renato Paes Leme. Feature-based dynamic pricing. Management Science, 66(1 1):411 1144211-499 4943, 2020.
Arnoud Den Boer. Dynamic pricing and learning: historical origins, current research, and new directions. Surveys in operations research and management science, 20(1):1-18, 2015.
Yuan Deng, Jieming Mao, Balasubramanian Sivan, and Kangning Wang. Approximately efficient bilateral trade. In STOC, pp. 718-721. ACM, 2022.
Yumou Fei. Improved approximation to first-best wwoo--rrotteeeee In International Conference Web and Internet Economics, pp. 204-218. Springer, 2022.
Martin Grötschel, László Lovász, and Alexander Schrijver. Geometric algorithms and combinato- rial optimization. Springer Science & Business Media, 1993.
Adel Javanmard. Perishability of data: dynamic pricing under varying-coefficient coefficient models. Journal
of Machine Learning Research, 18(53):1-31, 2017.
Adel Javanmard and Hamid Nazerzadeh. Dynamic pricing in figh-dimensions. Journal of Machine Learning Research, 20(9):1-4) 2019.
11

---

Published as a conference paper at ICLR 2025
Zi Yang Kang, Francisco Pernice, and Jan Vondrák. Fixed-price approximations in bilateral trade. In SODA, pp. 2964-2988 SIAM, 2022.
N Bora Keskin and Assaf Zeevi. Dynamic pricing with an unknown demand model: Asymptotically optimal semi-myopic policies. Operations research, 62(5): 142-1167. 2014.
R. Kleinberg and T. Leighton. The value of knowing a demand eurve: bounds on regret for online posted-price auctions. In 44th Annual IEEE Symposium on Foundations of Computer Science (FOCS), pp. 594 605, 2003.
Tor Lattimore and Csaba Szepesvári. Bandit algorithms. Cambridge University Press, 2020.
Renato Paes Leme and Jon Schneider. Contextual search via intrinsic volumes. In 2018 JEEE 59th Annual Symposium Foundations of Computer Science (FOCS), pp. 268-282. IEEE, 2018.
Allen Liu, Renato Paes Leme, and Jon Schneider. Optimal contextual pricing and extensions. In Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 1078.1078. SIAM, 2021.
Ilan Lobel, Renato Paes Leme, and Adrian Vladu. Multidimensional binary search for contextual decision-making. Operations Research,
2018.
Preston McAfee. The gains from trade under fixed price mechanisms. Applied economics research bulletin, 1(1):1-10, 2008.
Roger B Myerson and Mark A Satterthwaite. Efficient mechanisms for bilateral trading. Journal of economic theory, 29(2):265-28)) 1983.
William Vickrey. Counterspeculation, auctions, and competitive sealed tenders. The Journal of finance, 16(1):8 -7, 1961.
Jannyu Xu and Yu- Xiang Wang. Logarithmic regret in feature-based dynamic pricing. Advances in Neural Information Processing Systems, 34:1 2021.
12

---

Published as a conference paper at ICLR 2025
A BASIC FACTS ABOUT ELLIPSOIDS
An ellipsoid E' with center E R and positive definite matrix M E IRdxd is defined as
E(M, c) (a: E Rd || cllM- S 51}.
Given an hyperplane H(a, c) = for Rd a - c) v 0}, the minimal volume ellipsoid containing K = ((M, H (a, c) can be computed in closed form as follows. The new center is
1
d'
Ma,
d+1
Va Ma
and the new positive definite matrix is
d²
2
Maa M
M'
M
de
d+1
Ma
Then, the Löwner-John ellipsoid LJ(K) of the half ellipsoid K is the ellipsoid F(M', .c). Going from E(M, c) to E(M', d') the volume shrinks by the following amount:
vol(E(M', cd)) S vol c)).
An in-depth analysis of these results can be found in Grötschel et al. ( (1993).
B PROOF OF PROPOSITION 1
Before proving Proposition 1 we begin by provide a high-level view of Algorithm This algorithm maintains two ellipsoidal uncertainty sets Et and E (see Appendix [A] for some basic facts about ellipsoids). The key idea is that, at each update, the volume of an uncertainty shrinks "fast enough" to yield good estimate of the true parameter in a small number of iterations. The problems of computing the maximum and minimum possible valuations of the seller and buyer (Line admit simple closed-form solution (see, e.g., Grötschel et al. [1933 Chapter 3)).
At each round I, given the current uncertainty sets we compute the maximum and minimum possible valuations of the seller for the current product as
$t minge x. and St max aTB.
The maximum and minimum possible valuations of the buyer, denoted by b. and b, are computed analogously. All of these optimization problems admit a simple closed form solution (see, e.g., Grötschel et al. (1993] Chapter 3)).
the smallest possible valuation for the buyer by is above the highest possible valuation for the seller 8, (Line 5). the algorithm can post any price between these values, ensuring that the trade will occur. If 8, and & are far apart (Linel6)) the algorithm performs a binary search step (a.ka. "explore" step). and posts price pt which is halfway between the seller's 's minimum and the maximum possible valuations. Then, we update the seller's uncertainty set as follows: if the seller accepts the sale, it implies that x 0 S Pt. and we define the half-ellipsoid Ki41 = E n x 0" S P: Otherwise, we set Ki41 F3 n (0 : x 6a > pt). Finally, we round this half-ellipsoid by replacing by its I Löwner-John ellipsoid, i.e., the ellipsoid containing K2t1 with the smallest volume. We proceed similarly for the buyer (Line If the highest and lowest possible valuations of both the buyer and seller are close each other, and the buyer's minimum valuation is lower than the seller's 's maximum valuation, then the difference of valuations between the two parties is small, resulting in a negligible gain from trade. Therefore, in this case, we can safely post arbitrary price (Line 12}.
Proposition 1. Assume that the seller's 's and buyer's 's valuations follow Equation (2. Under Assump-
tion 1 Algorithm I with ABd2 / has regret bounded by RT < A0 log (20(d + 1)Td-
Proof. The proof of Proposition relies the fact that when the algorithm updates Ej or EP. it behaves as the ELLIPSODPPRCING algorithm Co et al. (2020). More precisely, we first note that under Assumption [ Fij and F contain 0² and 0", respectively. Moreover, straightforward
13

---

Published as a conference paper at ICLR 2025
induction shows that if Ej contains 8", then k2t1 also contains 6", and does E (similar reasoning applies to 0 and F.).
This implies that for all rounds, St S St is verified, we have 8, I Pr I by. and so the instantancous regret at that round is 0.
and by be by In particular, if the condition in
We also underline that Algorithm 1 oonyy explores to estimate 0* (Line if the condition
max x 0 BEE
min 0 2 AEF
is verified, equivalently if
2 0
max E
min
0
B
DEE
B
B
Since the normalized contexts 24 B are bounded in norm by by Assumption I 1 by Cohen et al. (2020). This Lemma states that Algorithm| [ will execute the steps in Lines 7 at most 2d A
we can apply Lemma
times, after which the condition in 6ine will never be verified again. A similar reasoning allows to bound the number of exploration rounds for the buyer's parameter 8 (Line 9.. Therefore, the total number of exploration rounds is bounded by 2 x 2d log( +
1)/ We notice that Assumption also implies that the valuations are in [-AB, AB), and so the instantaneous regret is bounded by ZAB. Thus, the regret of the exploration phase (Lines 6 and 9 bounded by 8ABd (og(20.A(d 1)/5))
Finally, if the conditions on Lines
6 and are not verified, it implies that
b. 8 S 8t
< b + +
< 2c.
Then, the instantaneous regret at that round is at most 2t, and the total regret for these steps is most 2cT. Choosing ABA yields the result.
C PROOF THEOREM
In order to prove Theorem we provide more detailed version of the EXPLORFFOR-COMMMT algorithm in Algorithm 5 Note that we adopt the convention 1/0 +00.
Before analyzing the EXPLORE-OP ORRCOMMIT algorithm, we define the various quantities used within Specifically, TH represents the set of indices from previous rounds that were dedicated to estimating the parameters 0 and 0³ (Line 8) We denote by 0 and 0e the estimates for the param- eters, and V, the corresponding empirical covariance matrix the beginning of round t. The set T contains the indices of the rounds used to estimate the integrals and J (Line 13). Moreover, 7h is the estimate of T(ke), and Jh is the estimate of J (kke). The quantities f* and D* represent our estimates of Ft (ke) and D (ke), respectively.
We use the following lemma to bound the total duration of the parameter exploration phase (the proof can be found in Appendix E.2p.
Lemma 4, Almost surely, the length of exploration phase T is bounded as
d log (Ta4)
T
112
The following lemma provides bounds on the estimation errors for 0", 0%, I, J, F*, and Dd for the
values of p. Timl, and TDD specified in Theorem Let E be the event
E = Vk K., V8 T U
x. (0) 8b)
< and
r. T (0: 0*)
< and
7 I (ke)
2e and
7 - J ((k)
$ $2c
14

---

Published as a conference paper at ICLR 2025
Algorithm EEXPLORE-OR-CORE (detailed version)
1: Input: parameter μ 0, length of exploration phases Tint and TFD, discretization size c, confi-
dence level 8.
2: Initialize: 7ith = Tim = Ø, 8j = 0g, 8 = 0g, V1 = la, K = [2P/c] 3, KC = -K
Th = TH = Ø for all & K., F = D 0 for all lo E K.
3: while & < T do
4: if | > μ then
DEsttmmate the parameters 6 and 8*
5:
Draw ~ 2111 P. Pl) and post prices (Pt.Pt)
6:
Update pur + T: pat U {t}
7:
Update V
Σ maee + IET
8:
Update parameter estimates
1 Mp x1) 2)
1 I s bi)
01+1
2PV 6+1
Σ TET
0iz1 22V ++1
2 x7
LET
9:
else if | < Timt then
EEstimate the integrals I and J
Draw Pt [[[[[P Pl) and post prices (pe.Pt)
11:
Update T <- T (t)
12:
if [Ti" = T then
Compute estimate of integrals I and J for k E K. do
14:
T
2P T LET
Σ
TTMee
I1
+ xj 0 S pt
bi
2P Tint Te7
Σ
Sm S f Ske
else if for some & K. |T
TDD then
DEstimate Fk
16:
Set T T + ke and post (pr,Pt)
Update The t T {t)
T = TFD then set
2P Tro
Elery fsr S pp)
else if for some hs K., [TP) < TD then
DEstimate Fr.
20:
Set = v, go + ke and post (pc.Pt) Pt)
21:
Update T Th U {t}
22:
if TTP TD then set
D = THD
2P EiETp Sb)
else
DPost greedy price
xI (0) B3
24:
set Ar (KiK))
25:
k; arg (MM
T' pale Ih Ba
Set p: x. 8i + k and post (pt,Pt)
15

---

Published as a conference paper at ICLR 2025
Let us define the exploitation (i.e., commit) phase
T = 12M
T
T UTiM
U KEX
(T
Moreover, let gEOC be the event
gEoc= = E ( KK VE VE pt (bb)) S (I. 1)e and D+ - >>--D((k)) s (I. (1.++)c) 1jc
Then, we can lower bound the probability of event FoCC as follows (the proof is postponed to Appendix E.3)
Lemma For the choice μ =c =<(Pvaloon (1+22T) + + Tim 8p2 (p@llg(1///) log(1/8)/ and
TED = =l0g holds that
(EEOC) 2
28 -8K(KK + 1).
Note that the choice 8 = (T(74 32P ensures that the event EEOC happens with probability at least 1 7-
The following Lemma bounds the error for estimating the gain from trade of a price p x 0g + ke on the high-probability event eooc (the proof is presented in Appendix E.4).
Lemma 6. On the event gboc, for all E TC, and all (k: k') E Ac.
7h + KK EGFT( x 02 + ke) < (10PL+4P+77
Next, we bound the discretization error. Let us define
(kī k/y) E arg max EGFT x, 02 + KE).
(
Then, the following result holds (see Appendix E.5 for its proof). Lemma 7, On the event EoC, we have that
max EGFT p) EGFT x 0z + kjte) S 2LLP..
We are now ready prove Theorem For p R, x E Rdd we define
A
max EGFT p') EGFT( p). p'
We begin by decomposing the regret as
RT
Σ A(Ir,p)) +
Σ A(x
TM
t
Σ
Σ (xt, Σ A(se.Pe) + Σ (at,
KEK
LETE
LET
tET
Using the fact that A(x,, Pt)
2P, we obtain
Ri S2P (1774
Tint + 2)K]T=D)
+ Σ A(Tr,P)).
LETC
dlog
(td)
On the one hand, Lemma implies that |T s
For the choice P
4²
e P (dllog
(+trr) 1/2 + Tim 8p2 822 log(1/8) and TFD 2log(1/0)e 2, this im-
plies that
2
(T+d)
1 1+ B2T
Ry <2Pdlog
("d
p dlog
+ A
c 16P 1og(1/8)c-2 2+
4P +9)
8P
1og(1/8)c* + Σ A(t,Pt).
tETC
16

---

Published as a conference paper at ICLR 2025
Note that the first term is of order e when is small enough. On the other hand, the event &oOC by Lemma
7
we have
Σ (at.Pi)
1E7C
E
A 00 kge) +
Σ
EGFT + kÇe) EGFT kee)
1ET
LET
$ +
Σ
EGFFT xj 0 + kfc)
EGFT 04 + k(e)
LETC
Moreover, our choice of kt ensures that for Ky such that (ki, K2) E Ar
Pu Thh D4 pdl. pri Thi Ar
By Lemma 6 this implies that, on event FEOC
EGFT( x, 02 + k)c) EGFT( I. 0r kac) S (20PL 14)c.
Thus, on the event go
2
R4 S2Pdlog (T+))
1 B2T
B2T
P/ dlog
+ +A -² 16P log (/6))/
d
8
+ +PP _ +3) log(1/0)e 2TLP - T(20PL + +P 8P-8-+10 14)e.
Substituting the values of and 5 as Theorem | and using Lemma 5 allows us to conclude the proof. In particular, the result in Theorem holds with Ö = 22PL 26P + 15, provided that > + 32P, that T 1 + B², that d, 5 log(T) 2 1, and that 16 + 36 S T1/1 log(T))//4
D PROOF OF THEOREM
D.1 DETAILED ALGORITHM
In order to prove Theorem we provide a more detailed version of the SCOUTING BANDIT WITH INFORMATION POOLING algorithm in Algorithm 6 Note that Lines 16 an 17, we adopt the convention 1/0- too when computing the upper- and lower- confidence bounds for increment levels k. K that have not yet been selected.
Before analyzing the SBIP algorithm, we introduce the different quantities appearing in the algo- rithm. In words, T: is the set of indices of the previous rounds that have been spent estimating the parameters 4 and g at the beginning of round t. Similarly, 0;, 0. and V, are the estimates of the parameters and the corresponding empirical covariance matrix at the beginning of round The set Tiat consists of the indices of the rounds used to estimate the integrals I and J. Moreover, 7 estimates [(k)), and j estimates J Jkk). The quantities F. and D represent (kcc) and (kc) at the beginning of round t. Similarly, No (resp., NNL counts the number of rounds in the successive elimination phase where the increment - 2 0g was equal to ke (resp., where the increment Pt pz-22 2 0 was close to ke), and where gained information on F*(ke) (resp., on (*e)))). The set A, collects the pairs (k, k') E KC such that x; 0; the Rs x + k'k is a possible price (within [-P, Pi). Then, for (k, k') E Ar, the quantities UCB, k') and LCB, (k, k') provide upper and lower confidence bounds on the expected gain from trade corresponding to this price.
estimates of
The third phase is successive elimination phase: each round, consider a set of possible op- timal prices, with corresponding upper confidence bound larger than the highest lower confidence bound. This set is denoted by K,, In order to ensure sufficient exploration of all potentially optimal price increments (ke, k'c) for (k, k') E Kr,, we choose the price increment with the widest confi- dence interval: this corresponds choosing the pair (k, Kr, such that either N.s.E Nf.
17

---

Published as a conference paper at ICLR 2025
Algorithm SCOUTING BANDITS WITH INFORMATION POOLING (SBIP) (detailed version)
Input: parameter μ1 > 0, length of scouting phase T discretization size e, confidence level
2: Initialize: 71"H = 7 = 2, 0 = Oa, 8 Og, V1 = Ia. K [2P/c] + 3, IC = [[K, K]], THE -T = Ø for all &o E K. NI N 0 for all k E K. Ft DJ = 0 for all k E K.
3: while - do
4: if | then
DEstimate the parameters 0 and 0*
5:
Draw pt (1-[p Pl) and post (Pt,Pe)
6:
Update T T,.t Utt
7:
Update Vi+1 = (EieTen mरेe +1s)
8:
Update parameter estimates
0141 = 2PV (+1 Eiery, (Lei S $1} 2) an, 0i41 = 2PV e41 Eiery (Li S b1 - 2) æ
9:
else if | < T then
>Esttmate the integrals I and J
10:
Draw ~ 2([- Pl) and post (pt.Pe)
Update Tim T in (t}
if [Tini Tint then
13:
for k: E KC do
n 2P EieTin I [Re x xT spss J 2P
EieTiL I S xT
14:
else
Run Successive Elimination
15:
Set A₁ =
: (0] (0: (01-):)+kep) +c))+
16:
for (k:,h') E A, do
UCB k') = Txx 1 + J D. + +12PL+7)++22 /2log(1/81/Nx + /2log(205//N22*
LCB, k²) = 1' F: + JD (12PL 7)E 2P
222l2((100/207 + 2
17:
Set KG, = ((k, K') E A (C K) max (Lx(L : (1,1") E Arl)
Set kj arg min No* kk, Ke ). and ke = arg min N (k, E k.}
18:
if No < bi then
19:
k kj, and set K to be such that (ke, kf) E Kr
21:
T,k = T Ut}
22:
else
k/ ky and set to be such that (ke, Ky) E Kr
24:
TE = T.E U {t)
25:
Set x.7 0; k and post (pt, Pt)
26:
Update Fly, =
Nye. pike Sp..
& 2+1
N11
27:
Update N = N + 1, and N 1+1
N.K.b Kg,
+1
Quantities that have not been updated during round are kept the same for round +
18

---

Published as a conference paper at ICLR 2025
is the lowest of the set. We denote (ke, ky) the pair of increments chosen in such way. In order to analyze this phase, we store the indexes of the rounds where we chose this pair because NV was the smallest in the set Te Analogously, the rounds where chose this pair because N bob the smallest are stored in the set T
was
D.2 REGRET ANALYSIS
The beginning of the proof of Theorem 2 is similar to that of Theorem | we define the event
As in the previous case,
= Yk E IC, Vt $ T41 UT!.
x (0: - 8h) S e,
2 (0; 8*) Sc e,
N - I [KE)
- 26,
jr [ike) s 26
Moreover, define event SBIP
EBIP & n {Ak EC, vt & 7 UT
Ft. - FT(ke)
2log(1/0] Le,
N.
D (*(K)) S
2 log (1/8
+ 2LEJ.
N
The following Lemma shows that the event @SBIP happens with large probability. The detailed proof can be found in Appendix E.6
Lemma 8. For the choice μ P(dl0g ((g²r) 1/2 + +A)
and T = 8p2 log
holds that
P (ESBIP) 2 1 - 28 - -4(2K + 48(2K + 1)T.
Note that the choice 5 = (T(38 + 16Pc 16
ensures that the event SSIP
happens with probability at least 1 - T-1
The following Lemma (whose proof located in Appendix F.7) shows that the upper and lower confidence bounds used in Algorithm 6 hold conditioned on the gigh-probbbility event ESBI
Lemma 9. Under the assumptions of Lemma 8 and conditioned on the event SSMP we have that for
all & T44 U Timt and all (k. k') E A.;
LCB, (k, W) S EGFT x. 07 + kc) S (k,)();
Moreover; it holds that (ket k()) Kr. where we recall that
(kt M(*)) E arg max EGFT(#, x 00 + ke). (k,k")
Finally, we bound the number of times sub-optimal price increment ke can be selected. For p IR x E Rdd recall that we defined
r (xx p) = max EGFT p') EGFT (2.F.
Lemma 10. Conditioned on the event ESBIP ift TSE then the following condition holds
llg(11/8)
r(Ie,P) < (50PL + 28)e + 16P,
No.
Similarly, iftt TSE. then the following condition holds
llg(118)
r(I,,p)) < (50PL 28) + 16P
No.
19

---

Published as a conference paper at ICLR 2025
The proof for this result can be found in Appendix E.8
We are now ready to bound the regret of SBIP. We begin by decomposing the regret as
RT
Σ
Σ
P()
Σ
r(rt,
1ET
1E7
NET7+1U7
Since the gain from trade is bounded by 2P, this implics
Rr 2PPTTT
2P|7
E
r(se,
IET
14TT,, UT
Then, using Lemma 4 by setting f = c ((p(dlog (1
1/2
+ =1)
and T
8P2 log(//// we have
T T+d d
(p
1+ B2T 12T
RT 5
2og
(-8 8
+ +
+
16c 1 2p log(1/00
Σ
r(xe,
(7)
t EET UT
To bound the third term (i.e., the regret of the successive elimination phase), we decompose it as
Σ
r(ar,Pic) = =E Σ r(xt,Pt) + Σ Σ
r(x..Pt).
LET UT
REK
KEK IETSE
For IC, let us partition Tit as follows. We denote by 7.SE = 8,k
SE and we define ti..... tr
the rounds where TSE More formally, we have 1 l2 < ... 1y75 and (.., Lage } T T,,. We define a -- logg (2(50PL + 28)e) and for [1,a]. we define
t, = 2log(1/6) (32 2
With these notation, we have
Σ r(1),P)) = Σ
r(Et;;
TETSE
S
Σ
r(tr,Ptt)) +
Σ
P(tt.sPt.).
L ATME SiSt. /1ATE
(la STS.
For a, if t. Sig
SE s.k by definition of t., we have
2 (1g))
2 2
(50PL + 28)e S 16P
No
and Lemma 10 implies that, conditioned on the high probbbbbbayility event SBIP
r(E,,Pt) -
Using the fact that (I) < 2P, we obtain
7-1
Σ ((),))) s 2P4 +
Σ 2 (lo+1 [t] + +1- T
1 2.
$ 2P4 + Σ a
(la+1 1/ +1) +- +1++)222+ .TSE
a=1
20

---

Published as a conference paper at ICLR 2025
Then,
R-1
8-1
Σ
2 a
(lo+1 - (a) = 6log(1/6) (32P)*
2
6 log
(0/() /0) (32P)² 2 2
logg(1 /6) (32P)²
S
(50PL + 28)
Moreover, we have that
2- T 2(50PL 28)
Therefore,
r(t,,P)) S 1P (og((1/))) -(18P)) + 3lo((1/0) (32P)²
+1+ 2(50PL+ + 28) (50PL + 28)
TET
We proceed similarly to bound EIETA r(æ,, Pt). and we obtain that
3 (32() Σ pt),, < 4P log(110)) (128P)²
+1 2(50L 28))7
(50PI. 28)
AE TE
Summing over l E K. and k' E K. and using the fact that ΣREK
5,k
+
TSE S T, we find 6,k
3 log (log(111)) /6) x (32P)²
r(c, - 2/AC|
4Plog(1/0) x (128P)² +
+1
(50PL + 28)
11UTH
2(50PI. 28)
(8)
Combining Equations 7 and 8), find that, conditioned on the event SRIP
2
2Pdlog
Itd) (P Flylogg/ (1 B2T
18 log(1/6)
Rr $
2²
2²
3 log (32P)²
+ 2///| 4PPogg(1/)) (128P)² + (50PL 28)e
+1 + 2(50PL 28)e2.
16P 16PP (itPP--)(( )T + 1)²) and using the definition of By setting = (d (d log((T)) and (338+
XC, we find that there exists constant (" depending on A, B C, and L such that with probability 1 207 2/3
Rr S ('ddlog(T)T))'.
This concludes the proof of Theorem Note that we can choose Č = 46111 P3 + 100PL 56, and
the result holds provided that T is large enough (namely, that T 2 2(38 16P). that 10 P/c, that p2 16 (og A, that pd log(T) 1, that Ba s T. and that (T/ (T)) >
3
3312 /002 x p2).
E PROOFS OF AUXILIARY LEMMAS
E. PROOF LEMMA
Lemma 1. Under Assumptions 7 land2 2 the expected gain from trade for x at price is given by
EGFT (x, p) = + ('6
(4)
where 8² == =T,00, 86 p- x 0. T(6) _e 1d (u)ddu and J(Ø) == __c (u)ddu.
21

---

Published as a conference paper at ICLR 2025
Proof. The proof relies on the characterization of the gain from trade given by Lemma 4.1 in Cesa- Bianchi et al. (2021). Recall that, under Assumption | we have ç E [-C, C.. and & E [-C, Then, denoting f and f the densities of ç? and c we have EG
[ G= C0-CTTTTe (b 8) S / -0
s) ds db.
Let f b (x - s) and f : (x 0r 8) be the densities of 8 and b, conditionnally
on x, and note that outside of (x: 8 C, 0 + C| |x T 0 C, To + (s) 0. With these notation, we have
EGFT(#,)) = 1
(..b)et-PPMp (b - 8)l{s 3 x - b) f (s) ds
(G.D)EI-PPPIxlP P.plx(p.1 -lanset-Paatemm
([ S" du f)) ds db.
Thus,
EGFT(x;,)) p) [ |IPPI (LEDEEE-RAADAN fb) ds db du
- S-PAl (JSOEEENNN
((s)F((b)) ds db du.
This yields
EGFT(2,,) 1 P-p (Lennet-PAMm
(ss ds du
+ -mam (eaoeet-AAii
('s) ds db du
f ds db du.
This, in turn, implies that
1 P.pl (LeNEEERAAMe (*s) ds db du
EGFT(r.P)
+ Sm (JasNEt-
(s) 2h (b) ds du
I (O(b) dd
[ [(-Pa) [-Paal
(s) ds
+ 1-Pel
(s) ds
(b) dbdu.
J.p.M Ju.M
Jb.
By using the change in variables e* -- 0=, u0 = u-x To0 10 5b b--xx To and wb u-xx u-= TO and the definition of ja and شo, we get
f(5x) dd [ [-P.p] /
EGFT(#,P)
(- f(E") du
(1.P)) S (o f(Et) de du
| P ((E))E"
f(5)) ded dEb
(-P--x J-----Tmpp--0001--- 1- f(5*) de* du
Ip P
+ J|-P-a -o-----0-p--- 00
[("))("
To..TOpPP--TT 00 100
Pu 1ow
S(E") deh du.
22

---

Published as a conference paper at ICLR 2025
Now, under Assumption
1 f and f are null outside of [-C,C). Moreover, P xx xT C and
-P x 8 -C. Thus.
EGFT(x, = - p f(E") dd I J-CGp-oTor J f(5*) de* du²
+ 1 C-Cp--TT0 )(5") [ J I /n0.c S(E") de du
=D - x xTO p po-sioo (d("))duu + (p -
f
Pp-xxTTp xT00)
D2 (
p-zTon
Using the definition of 8 x To 0 and 80 --xx"p TT, we obtain the desired result.
E.2 PROOF OF LEMMA
Lemma 4, Almost surely, the length of exploration phase TT41 is bounded as
dl log
(TaA)
17
122
Proof. The elliptical potential Lemma (see, e.g., Proposition in Carpentier et al. (0020) implies that almost surely,
T++1 + +d
Σ | ||
(Ererpe 2107 +1o) +1=)-1 17F+i log
TET
Since for all E T
||0||||
E EieTpe 21077 +ls) 2 μ. this implies that
par T+1
[T44ldlog dlo
d
Now, almost surely, [TF S T. This implies in particular that
dooog
(T--d)
122
which concludes the proof.
E.3 PROOF OF LEMMA
Lemma For the choice μ = (P (1+22T) + +A)=
Tint 8p2 log(1/)/) and
TD = =2log(1 2log((16)) it holds that
(gEOC)
2 1 28 88((K + +1).
Proof. The Lemma is consequence of the following two auxiliary results, bounding respectively the error for estimating the parameters H and 6¹, and the integrals and J.
Lemma 11. Let En be the event:
El = VE & T
(0) (0:00-00) Se and (0; -00) see.
Then, for the choice μ = (p(dlog (orlggg++12))
3/2 +
A
we have IP (E1) 2 1 1 1 28.
The proof of the above lemma is deferred to Appendix
E.9
23

---

Published as a conference paper at ICLR 2025
Lemma 12. Let Eg be the event:
82 = [T Tum or WAAA E - (Ike)
- 2r and 5t - J(ke) s 20 NE1.
Then, for the choice μt = P((dlog (1tger) 1/2
-1 + +d)
and Tine 8p2 lop2l//1//)/ we have
PP ((2) 21 28 45(2K + 1).
The proof of the above lemma is deferred to Appendix E.10
Next, control the error | F (kE)) uniformly for k E K. The results for DD (kE) follow from similar arguments. To do so, we rely on the following well known result (for the sake of completeness, we provide proof in Appendix E.
Lemma 13. Let (yt)es 1221 be sequence of random variables adapted for a filtration F such that E Fer [m, M.. Assume that for t N.. E {0, 11 is Fe-1-measurable, and define
N₂ == Eige 4, and the = N₂ Eist 4(y1 IE [E if Ne 2 1. Then, for any E N4, and
6 E 10,
log(1/0) 2N
P
N: 0
[hd S (M m)/
2 1 218.
Moreover, for any t 0 and E 10,
log(1/6)
P N₂ =t t and 1p 2 (M- m))
< 1 26.
2N,
For t T, define 4 I[te E Th J. i
[ss S pe), and observe that for Fi ((11,.. T1+1. (T{8) I SPi),T( & p1) pi))..... (T{,, S pr). I(b. S sp.))). 4 is Fi---meaaurab.ll
and yr is F, adapted. Moreover,
4E Me
Fi-1] 4PP
(x,
+ E S x 0 ke
4 F
xr 03
0r) + he
Using Lemma 13
we find that with probability 1 - 26, either Th < TD
ExscuE" 4F
[2] (0: 8:) + ke
2 log(1/0)
TFD
TDD
Moreover, on the event E,, for all / & Tarr we find that
|o, (0: - 0.)l < e. Using the fact that F is L-Lipschitz
pd
0j
8z
+ kc
Fd (ke) s Le.
Thus, with probability 1 - 28, either [T
TFD
210g(1/8)
F'((k))
+ Le.
TFD
Using Lemma I1 and 12 along with a union bound over & E X. yields the desired result for the choice FD 2 2ogg1100
24

---

Published as a conference paper at ICLR 2025
E.4 PROOF OF LEMMA 6
Lemma 6. On the event Eboc, for all E T and all (ki, k²) E Ar.
1 F* + DaD EGFT(I,, 2, 03 + kε) - (10PL + + 7)E.
Proof. The proof relies on the following result:
Lemma 14. On the event gETC, g all (k, k) E As, and p = xz. 0g + ke, we have
EGFT(( (T f. + 7th Te & 6PLe + 3e + 2P | + 3D1) + 11 [JJ
where we define ÂI = I(K')) - 1M ÂJ = (kke Jr, ÅF F (kE)
FRt ÅD D(W') DM.
The proof of this intermediate result is in Appendix E.12
To conclude the proof of Lemma 6 it remains to bound the gaps ÅF, ÅD, ÅI, and ÂJ on the event gETe, By definition of the event gare, on this event Á/ 2e, DD (L+ 1)e, AJ s 2e and ÅF < (L + 1)e. Thus, on the event CETC,
EGFF(T p)
( T & 6PLc 3 4P + 1)e + 4e.
This concludes the proof.
E.5 PROOF OF LEMMA
Lemma 7. On the event FOOC, we have that
max EGF EGFT (2,, (2,, T0; + kTe) 2LP..
Proof. By definition of Ar,
sup EGFT( 2 EGFT(I,, x. kze)). pEl P.P.
Since the mapping p + EGFT p) is continuous, we can define
pf x 02
22 T
0:
0.:
+
he
pi E arg max EGFT(Z,,) k;
and Re
We now show that (R,, k() E A.. By Lemma we have that p; xx, 1-00>-00 -C', and pt xz 8b < C (otherwise EGFT( P. 0). This implies that pt n, Ha [-2P, 2P,, and similarly that
Pe xr7 8 [122
On the one hand, on the event SETC |1T (0r (o=) = so
x ,, 0; E 1-2P--c,PP Thus,
k K.. On the other hand,
zr 0 6.)
+ Trse = (
TØ: 02 + hic pi) + (p: - x, 00) + xt T
-p:)
Then, on the event gETC.
x, T 0i -r)) 1&c 2P-2P-20 2c, 2PP-2c,2PP +2]
- so K/ [-2 - 3c,, 2P + 3c]. Therefore, K E K. This implies that (ke, R() E Ar, so
BGFT (wt, x 0 k) 2 BGFT(#,, x 0z + kze).
Finally, Lemma I and Assumption 2 imply that the function p + EGFT(*;.P) is 2LP-Lipschitz continuous. This, in turn, implies that
EGFT pF) EGFT(2,,, TT0; +ke) S 2LPe.
This proves the statement.
25

---

Published as a conference paper at ICLR 2025
E.6 PROOF OF LEMMA
Lemma 8. For the choice μ (P(dlog
1/2 (= (2
+ A
and T = 8P2 log(1/0)/e it
holds that
P (ESSBIP) 2 1 2 + +1
48(2K 1yT.
Proof. The proof relies on Lemma 11 and 12
On top of these results, we have to control the To do so, we rely on Lemma 13 For f S T, k), Yt = 1( S pt). and we note that for Fi = (U[ss: S pcb. pt H)). 4 is F mecaurablle
error |F (ke) uniformly for k E K.
we define = [t $ Tim T441 and l
((f1,.... #1+1, (1[s) S 1[b I pı)).....
and Yt F; adapted. Moreover,
4 I Me Ft-1] = 11I (x. 0r + E S o. 03 + kt
= =4bb"
a 0 0r) + ke
Using Lemma 13
we find that with probability
2ot, either N₂ = 0 or
Eesc4F*
24
07
8r) kt)
2 log(1/0)
Ft.
No
Nock
(where we recall that we adopt the convention 1/0 = oo). Moreover, on the event E,, for all of T Io (0: 8¹) < Since F is L-Lipschitz, this implies
|F 11 0; - 00) + ke) F" (ke) S Le.
Thus, with probability 1 - 28t,
F Fi(Kc) 2log(1/6)
+ Le.
No.
Using union bound over h: E K. and & Time U Th4 yields the desired result.
Next, bound D (kc)) using similar arguments. In particular, define II L & Tim U TTEH and ki = k.. 1/- (b. p.} and note that
4E Ie [1-11] 4PP (1,7 gh + c z x 0: + kee
Fi-1)
xT - x, xTT00 + kze.
k 1))
DD 0 80)
ke +e
By definition of Ar, we have that = 1, then -1, 0.
k. S Using the Lipschitz
continuity of D6, this implies that, conditioned on the event E,,
4 Ely Fr-1] (kc) < 2Lc.
The rest of the proof follows similarly.
E.7 PROOF OF LEMMA
Lemma 9. Under the assumptions of Lemma 8 and conditioned on the event EBIP have that for all & Tar U Tim and all (k. k') E A:;
LCB, (k. k') < EGFT x. T 03 kc) S (K,)(k,k)).
Moreover, it holds that (kt, k Kr. where we recall that
(k. k(r)) E arg max EGFT ke). (k.
26

---

Published as a conference paper at ICLR 2025
Proof. Let prove the first part of Lemma By Lemma 14 and by definition of the event ERIIP we have for all (k, k/) E A,, and all t & T UT
BGFT(Z - Td ph 3hh DD
2 1lgg(1/8)
2 1og((1/) N
s 6PL + +e +
(V
Noch
+
+ 3Le
+ 4e
(V/ 1lgg(1/5) No
2 log(1/5) N
$ (12PL + 7)c 2P
This concludes the first part of Lemma 9 The second claim follows immediately by noticing that by definition, (ki k()) Ar, and that, for all (k,k') E A..
LCB k' s EGFT xf ke) EGFT x of 09-+ kge) S UKB,
This concludes the proof.
E.8 PROOF OF LEMMA 10
Lemma 10. Conditioned on the event ESBIP, ift E Takk then the following condition holds
2 llg((18))
r( (50PI. 28) 16P
N
Similarly, ift E T then the following condition holds
llgg(1/0 No.
r(xt,Pt) (50PI, 28) 16P
Proof. Assume that t E T-S Then, our choice of ky together with Lemma 9 ensures that, condi- tioned on the event ESBIP
UCB,(ki, k)) 2 LkB,
This implies that
(k,, ky) + (UCB, K.)
( 2
UCB,(k; k(*) + (LCB, UCB k(*))
Using again Lemma 9 this implies that
EGFT(II; xT + kic) + (ke, k() LC,, K() KK) kk())
2 EGFF(TI, TT + kTe).
Thus,
EGFT(Z,, xT 15++Ki k(e) EGFT x 0 + kre) (UCB, K,) LCB, (UCB, M2) LCB, (kt, M²))
Then, conditioned the event ESBIP_
2log(1/00
2 2lo No.
(k,, - LC,, K4) S 2112 4P
No
Since / E TE 3,k*
we know that No > No..A. Then, we have that
2 (l0(1/))
UCB,(k,, K.) - LCB, (k,, k) < 2(12P1 7)c + 8P,
No..
27

---

Published as a conference paper at ICLR 2025
Similarly, since The we have that NoA 2 No and N₂ 2 No so we also have
l
LCB, (#) 2(22P 7)E +) 1
No
Thus,
2 2og(11/8)
EGFT x. 00 k) , 8" h(c) - 4(12PL 16P,
No
By Lemma 7 this implies
2 log(1/0)
2 0³ + Ric) - (50PL+ + 16P
V
Noc
The proof of the second claim follows from similar arguments.
E.9 PROOF OF LEMMA
Lemma 11. Let & be the event:
E1 = { Vt & TT41;
Fhe (0; - -00) / Se
and o (0; 8*) se..
Then, for the choice μ = (P(dlog (z=g22) 1/2
-1
+ =A)
we have IP (E1) 2 26.
Proof. Let prove the bound |or] (0; -0)- S with high probability; the bound [o: 00)
will follow from similar arguments.
We introduce the variables
ā = = {t E T and U: = 2P [441 (LOA S 5a) - -12
and the o-algebra F, = σ ((I1,... Iz+s, (1(s) <
S pii)).... (Lfs; S <p: 1: S p:))). With these notation, we have that oe and {t E T } Je-aaauurabl.. Moreover,
du
E 1i = Ifte T
2P
P < 8t Fr-1]
2P - P
=I E T
1-P [ x lr + {} (E) de du P)
dufo(E) - P)
=I(Le T
TT 0 + 1
=Ifte E T
x.
EF(()
=1fte E T f x, gr
where in the last equality we used that (T) E [c:] = 0. Thus, conditionally on Ft-1. Dr. J.J 00 is centered and belongs to [- P, PJ. which implies that P-subgaussian, Now, for
all / E .I,..., T}, we have
0: =P
Σ 1ET
Ito la
Σ TE
1ip 2 8t) - 1 x1
Σ
उंेे + 1d
Σ J
1st
Ict
28

---

Published as a conference paper at ICLR 2025
Using the fact that, for all t < 1, | I B and || Σ A, and applying Theorem 2 by Abbasi- Yadkori et al. (2011), we find that for all t 2 O, with probability --,, 6,
1 B2T
10: EET +1 & PV dlog
+ A.
Note that our definitions of ūt and j ensure that
110 - 0 E 2ιيe tha 110g - 00 x..1 B12T +1a"
Moreover, for all 4,
| (0; - 0-) S || 11
Eoerge, Tare thi) -1 10ū - -0"1l
(Eoerpp, 21x7 t12)
E
In particular, if & TT++1 ||=,||
S μ., so with probability 1 8,
Enerpe m1eT+h)
+ B2T
|x] (0; - -00) S 1 P Pyidlog
+ +A
+ A -1
For the choice = (P/dlog (L+.2TT)
this implies that
1 (0p 00) se
which concludes the proof.
E.10 PROOF OF LEMMA 12
Lemma 12. Let Eg be the event:
Eg = {(Timm) Time or VK 7 1 (ke)
S 2E and 1 - [(ke) s 26 NET
Then, for the choice μ = (P(alog
1/2
-1
+ A
and Tint 8p2 log(lg(11)) /8)/ we have
(E2) 2
28
45(2K + 1).
Proof. We control the error 7 1 (ke) uniformly for k S K; the result for J - ((ke) can be proved analogously.
For k < K, and t < T. let us define = I{t Tim). V1 = 2PI ke + 2 0 S s b, and
note that for F, = ((#1,.., Z141, (I{ss I I1b. I sp.))...... (Ifs: S I(b. mee---easrabll,, and yr a-aateeeed. Moreover,
S p.))), 4 is
E [[-1] 2PP he x. 0g Sp. S S [T
C
11 0h + u) (z) dg du
2P
2p
ketzTO 03
--
Db (u x.J 0h) du.
ketx 0r
Using the change in variables
= u - x 0b, this implies that
P-u. gb
F--1]
Dd (u')
ketx Tx 6
29

---

Published as a conference paper at ICLR 2025
Moreover, under Assumptions and Thus,
P zT h C and, for u' [C, P xT (n 0.
E 13 Fi-1l =
DO (u') du'
kkt -2
= [[ke + ze 0 x 0
Finally, note that yr 1E [vr is in 1-2P, Then, using Lemma 13 we find that
Tint and 7 EiErm / (ke+ z7 (0: - -00)
log(1/6)
P
|
2 4Py
25.
Tim
2T
To conclude our proof, note that the event & for all E Tim, |.a (0: 0001 c, so with probability 1 - 26, either (rint] < T or
ketz (0)-00)
| (ke + zi (0: -0)) I(ke)
(1- (*())( da
kr
T (0)-
dd
kt
0
80)
24
Using the same reasoning to control the error in estimating J, taking union bound for K., and using Lemma 11 we find that on an event &2 C E1 of probability larger than 1 - 25 - 45(2K' + 1),
either (intt
log(1/0) 27
T - I(ke)
S /PV
+
and
log(1/5)
Ih - J(ke) S APV
+
2T
simultaneously for all k K. For the choice TiM 8P2 log(1/0)/e we obtain the desired result.
E.11 PROOF OF LEMMA
Lemma 13. Let (14) be a sequence of random variables adapted for a filtration Fr. such that
Vt E [ (m, M). Assume that for &. N., 4 E {0, 1} is Fr-1-measurable, and define
N₂ = Eise u. and Th E='Ege u(1 [ 1]) No 1. Then, for any N. and
8 E (0,
log(1/5) 2N.
P N₂ 0 poal S (M mi/
> 1 2t8.
Moreover, for any
0 and (0,
log(1/8)
IP N; and lid| 2 (M ((--)) m))
S 25.
2N,
Proof. Let us define Z, = Eisuun - E Fi)) and for all E R let M, = exp (a 7, 2 N.) We begin by showing that M, is super-martingale. Indeed,
30

---

Published as a conference paper at ICLR 2025
have that
E ex u(v - -E F(vl)
Fi-1]
E [ exppfx(1 - E [v F(-1)))3 + (1 4d Fi-1
x² -m)²
4 exp
(1 (4)
a2 mm)
S exp
8
where we use the fact that (v E le version of Hoeffding's Lemma. Noticing that
Fi-1l) is bounded in [m, M] together with the conditional
22 mm)
M₁ M exp x culy E F(-ll)
8
this proves that M, is super-martinalee and E [M] E [MO] = 1.
Now, for all > 0 and all / E N, and all x > 0, by Markov-Chernot argument,
(Zz 2 E and N₂ = 1) = P (1 = 1] = 2 ESTT)
S e B (I (N. =1 e
3as شلل E [ = 13 = 22rns- m1)
Using the previous result, we have that
"h 2 PMM
1[N: = 13 E =7 22 m) P
E 1 [ 1) 6
=E
EE e aZ 22000mm-
E(M))
E(M)) = 1.
This yields
PP (Z+ 2 and N₂ 1) < -ex+ 13cne (1a)-
In particular, for e (M m)
(1/g( and 1(hd =
1 I-log(1/8) and N, =1)= =
P
Z. 2 (M m)
This proves the first part of the Lemma. Summing over the values of / from 1 to t, we find that
N, log(1/5) and N₂ 2 1 tō.
PP Zi (M m)
Similar arguments can used to prove that
N₂ log(1/8)
IP
Ze (M m)
2 and N 21 Stō.
In order to conclude the proof we observe that Z, = Nr we normalize by N₁, and observe that adding the N, 0 can only increase the probability.
31

---

Published as a conference paper at ICLR 2025
E.12 PROOF OF LEMMA 14
Lemma 14. On the event gETc, for all (k, E A, and x 0e + ke, we have
(T pk + 3 D*) 1 <6PLc 3e +P (AF)+ + ( +1 [JJ where we define ÂI I(Kc) IM, ÂJ J(ke) Jr, ÂF F(ke) FR, ÅD D(K'c) BM.
EGFT(Z,,P)
Proof. By Lemma 1 for any price p x 02 ke and such that (k, k)) E As, and 8" pp-z,
8 = 0% we have that
EGFT(I,,)) = (00
Then,
EGFT p) = (I(K'E) + 1(80) - I(WE)) ( - (kE)) +
(J(kc) J(8*) J(kc)) (D'( D)(K)))-
Moreover, by letting AI I(8 I(We), AF - AJ ((8*) (kk) and
AD = (" D this yields
EGFT p) =I(W')) + ((ee) AT J(6*)AD++++ (K
Since I and are bounded by 2P. and and D are bounded by 1, this implies that
EGFT( - (((W)))F'') (KE) + (Kk)) S AF + + + 2P/
Now, let us introduce ex = 8" ke, and c² = 8 - -kc. Then, we have
6" = no
T 03 kt) -(ke + xt TT
x ( 0²)
On event gETC we have le"l < e. Since F' is L-Lipschitz continuous, and AF = F* + +e²) F (ke), this implies API < Le. Similarly, J is 1-Lipschitz continuous, and AJ J(Ke + +e²)
J(kc), so |J] < c. Similarly,
e² =
32 02 + kc) - (x, 0¹ + +ke))
T (0; - 07,) + kt - k'e + x (0; - -0').
By definition of At, under the event EETC we have |e*| < 2r. Since D is L-Lipschitz continuous and AD = (W'' e²) - D*( |AD] < 2L.. Similarly, I is 1-Lipsehitz continuous, A/ I(k'c+e") - so this implies that A S 2c. Putting everything together, we find that on the event gEIC
(I(KE)))*(k)) + J(KEDD -) S6PLe 3e.
Similarly, denoting ÂL 1(kee) Tt. AD = D(Ke) - D As = J(ke) Fh and AF F(ke) - f we have
[(Kc)F -Kk) (i' +' F*DD) < + AT 2P 2P ÅD + (J
This concludes the proof.
32

---

Published as a conference paper at ICLR 2025
F MOTIVATING EXAMPLE
Lemma [ Tmmphsizes that the expected gain from trade at given price p depends on the quantities 8 = p 1 8- and 8 p 2, 6t. Remember that the difference in average valuations Á given by A x 06 -p--x
_, 0", and with this notation, 8 8 A. Therefore, the expected gain from
trade can be rewritten as a function of the pair (8", A). As an immediate consequence, we see that the optimal increment 8 only depends on the difference in average valuations A: if
0 + 8 x' T = x 8 - 0", then p' = x 0 + 8
maximizes EGFT(I, p), and x' is such that x' -"- maximizes EGFT(11. (GFFT(',P')) ,
On the other hand, the following example shows that there no explicit dependence of the optimal price increment 8 on the difference in average valuations A. In words, when A is small, might prefer to choose an increment 5 that leads to trade happening with lower probabilities but corresponds to higher rewards. By contrast, as A increases, similar values of the increment 8a will correspond to higher gains if the trade happens. Then, we might choose to post prices corresponding to smaller inerement 8* to increase the probability that the trade happens.
This reasoning demonstrates that knowing that an increment 8* is optimal for a difference in average valuations A does not allow to determine the optimal increment 8' corresponding to a different value A' of the difference in average valuations. This implies that to precisely identify the optimal price increment 8 for all differences in average valuations A, it may be necessary to have accurate estimates of the functions 5 and I for broad range of values of 8*, Similar arguments can be employed to argue that precise estimates of the value of D and for a wide range of values of 8 = A - 8 might also be necessary.
To illustrate this phenomenon, we construct an example where different levels of A lead to entirely different choices of the optimal price increment 8*, Specifically, we consider a scenario where, for certain values of ($1, $2, $3) E RR, (b1, by, by) E IR3, (01, Q2 (g)) in the simplex, and 0 > 0 (to be defined later), the density f (resp. f²) of the seller's noise 8 (resp. buyer's 's noise (*) is given by:
(6) 1(x [1 81 + 0 U [$2, 82 + + [53, 83 + 0}}
30
(8) T.T(x E (bi,b, + + a2 E (b2, b2 + +] + agllfar E (by, by + 0]}
0
The setting in illustrated in figure
We assume that ($1, $2, 83) and (b,, b2 ba) verify + < b1, b1 < s2, $2. + b2, by + 83, and 83 + 0 < 13. Then, it is straightforward to see that while A >> O, and A is small enough so that by + 0 A 82 and by + 0 A 83, the optimal increment belongs to the set (δ), 62, 63), where 61. 62. and 63 belong respectively to [s] + 0, 61). [s2 + 0, 62). and [sg + 0, 6z].
We also assume that 01 is much larger than ag, which in turn much larger than 0g. Then, the increment o, is such that the trade happens with the highest probability: indeed, if 8" = d > by. the buyer rejects the trade with high probability. For the same reasons, the probability of trade happening at an increment 8n is much lower, and the probability of a trade happening at increment d3 is the lowest.
Finally, we assume that 63 93 is much larger than b2 52, which in turn is much larger than 6 S1 Then, the gain from any trade happening at increment 8, is small compared to the gain from trades happening at increment 82, which in turn is small compared to the gain from trade happening at increment 63.
For some well-chosen values of the parameters specified below, when the average gain from trade of the seller and the buyer are both zero (x: 8- = xx 0¹ = 0), the most profitable increment dg: the probability of the trade happening is less likely. but when it occurs, it is more profitable.
Now, to obtain the probability of a price p = xT 00 +8 being accepted by the buyer, it sufficient to translate the cumulative distribution function (c.d.f.) of 5h (represented in Figure 1 by the quantity
A = xr T (@' 8*). In particular, when A > 0 is small enough so that bj + 8 A < 82 and by + 0 + A < $3, observe that, the one hand, the probability that the trade happens for the increments 8* e 8, 82, 63 remains unchanged; however, the corresponding gains if the trade occurs all increase with A. For some well-chosen values of the parameters, if A is positive but sufficiently
33

---

Published as a conference paper at ICLR 2025
01 A
3
2-
0
81
b1
82
22
b2
03
b3
Figure I: Illustration for the c.d.f. 1e and f corresponding to the example described in Section The c.d.f. f is represented in red, the c.d.f. fo is represented in blue.
small, the expected gain from trade is maximized by 8 = 52. When A is large, the expected gain from trade is maximized by choosing 8 = 8": in other words, this choice of increment ensures that the sale happens with the highest probability, and each sale leads to reward of at least A. In Figure 2 we plot the expected gain from trade for different values of A as a function of 8*, The values chosen for the parameters are follows: ($1, 82, $3) (0, 2, 6). (b1, b2, by) (0.01, 20), (a1, ar2, az)) (0.85, 0.11, 0.04), and
0.001. With these values, for A 0, the optimal increment is 8 10; for A 1, it is 82 2.5; and for A 1.5, is 8 0.01.
0.75
A
EGFT
0
0.25
0.00
0.0
7.5
10.0
Figure 2: Expected gain from trade for different values of increment 5 and difference in average
valuations A.
G PROOFS OF SECTION 5
Lemma 2.
For each round t T such that b, 2 it holds: ([PROHTT((L 901 where the expectation with respect to the choice of (pe, qe).
(b. (b.-s.) 8P log
Proof. To simplify notation, and since focus single round t T. omit the explicit dependence on from Pt, qr. 4, st, and b, We consider two cases. First, b < 2/1, the inequality immediately satisfied since the lhs is non-negative while the rhs is 0. Second, if > 2/T,
34

---

Published as a conference paper at ICLR 2025
let & be the event in which p [s, (s + b)/2]. Since p PI) Moreover, we have
have P(E) (b- s)/
1 log T
P
log
p
which is well defined since
8 8+b b
2
S b
T
Let Ex denote the event in which llog p))]. Under & and E' we get
b b-p
p p+b
--p+2- = - [oo((1((6-))) 2 + 2- (lo(1//0--))+))) =
2
2
Therefore, when 2 2
b 6-5
[[PROHIT(P:)]]
(q
2P log
+ b
2
P)
2
2P log T
(b - s)²
8P log T
This concludes the proof.
Lemma 3. For 2 log T, it holds with probability at least
1/T that
PROFTT((Pr.::) (T) [E[r]
Σ
Σ [E|T]
[be
811+
4 4P2 log(T)
bb. 81]+ 2. [E[T]
Proof. First, we observe that given the sequence (bc. kelT and a time step T, by Azuma- Hoeffding inequality we have that, with probability least 1 - d.
PROFIT, q:) 2 E[PROFIT((P.O)) g)] [E[T]
Σ
log(118)
Σ (b. - rE(T]
100--s1+1+ s1]+)2
Then, by applying union bound, the above inequality holds simultaneously for all possible with probability at least 1 - 8T. Then, by setting d = 72, with probability at least 1 - 1/7, , it holds:
PROFIT,
2 Σ
(ROFFI,, 9)1
Alog(T)
(lb +) [E[T]
Σ
*E[r]]
([b +)1 Pogog T
Σ
1lo((1/))
Σ
(b.. (1b--s]+7)) +12
(by Lemma
T
*E]r]
rE[r]
(lb. se) }22 8Plog T
4 (Tg(T))
Σ
(lb. - s1]+ 11+))=0 1
LE|T]
1 (bb. $1
=7 Σ
4 Alog(T) T
Σ (b+ sel -2
T
8P log T
rE[r]
1E|r]
2
T
[b, sz]+
4 log(T)
(Ibe -2 -2 (by Jensen's Inequality) *E(r]]
Σ
8P SPlog7 T
[E]TT]
a
1b+ sr]
4 (og((T)
Σ
(be - -0,sss1+ +1 -2
(by Definition
8P (T))
TE[T]
<E|T]
a
[he se]+
4p2 (T)
bb 8/ 2.
8P (P)og(T)
[E[7]
[E[T]]
35

---

Published as a conference paper at ICLR 2025
This concludes the proof.
Theorem 3. Given the two-bil algorithm A, the corresponding one-bit learning algorithm satisfies global budget balance and, with probability at least 1/TT, has regret
R
bit) < 0 (a 3T log T) + Rd
Proof. The one-bit algorithm is global budget balanced by construction (see choice of B). Then, we condition the high probability regret bound on the following events:
With probability 1 - 1/T the two-bit EOC algorithm guarantees number of exploration rounds smaller than [T and regret at most n2(2)
With probability 1 1 1/T, it holds the inequality in Lemma 3
By axuma-Hoeffdingg with probability at least
1/T it holds
max EGFT(
bb s1]+ + 16P27logl (T).
P
Then, the regret can be bounded as follows
Rr
max EGFT p)
EGFT(Z.,,P)
t=1
max EGFT
max EGFT EGFT(.I. pt)
P
t=
max EGFT p) 2T RT
(22)
P
[be - sss + 16622 + 2T + R(
<
1=1
$
Σ
bb $1] + aT 27 + R
<
2
[b s1st + + 2T R(
where in the socond-to-last inequality (). The last inequality is by definition of a on the interval [7]]
that, since 5 > B/2P, it holds that >
16P log T (by Equation
Then, by Lemma and since Ei s1}+ 2 Ei= PROFIT,(PL) qi) 2 2048P*a T, we have
(pe 2 (Pl
Σ bb. sel+ -bs+ t1|7]
4P2 log(T)
Σ
bb -s]] 2
[E]TT]
Σ
[b. sel+
8P2 log log (T)
Σ
[b st]+
(T)
tE[T]
[
[b. [0]
(6Plog(T)
rE]r]
36

---

Published as a conference paper at ICLR 2025
Then, since B v 2048P* 2 "og"'o" T and Σi= (POFIT,(PE.9))) - B 2P,,, by substituting in the expression above we obtain the desired bound on Eie(r] [b - sr] particular, we have
RT S 2
bb
s1]t + R/
t=1
32P log
PROFIT,(P: 9:) 21 + R2
pa log" T T 21 RT (2)
S
with M is numeric constant independent the problem instance.
H ALTERNATIVE ALGORITHM FOR NOISY VALUATIONS WITH TWO-BIT FEEDBACK
The regret of Algorithm is primarily driven by the estimation of the c.d.f. F and demand function D uniformly over grid of increments. We now present alternative sub-optimal approach. Specifically, to leverage the fact that the optimal increment 8 only depends on the difference in average valuations A,,
could first execute the sub-routines EST-PAR and EST-INT, yielding xzT6%, 8h, I and J up to precision using Ō samples. Then, we could round estimates of x 8 x;
the value of A on grid of size e and run independent Scouting Bandit algorithms (as described in CesaCeeaBaa Cesa--Bianchi et (2024) for each of the e rounded values.
The grid size implies discretization error of order O(e). The highest regret occurs when each of the c independent Scouting Bandit algorithms runs for the same number of rounds T, Tc. Each algorithm incurs regret ((r so their combined regret is Ö(T e 0/r -1/>) -/+). For T/4, this strategy also results in regret of order ((T))a)
37


Reviews:
[{"review_id": "t4JTPKzpwk", "reviewer": "Reviewer_Dy9f", "summary": "This paper tackles the bilateral trade problem in an online setting where there is an additional context present. At each time step $t$, a buyer and a seller arrive with private values $b_t$ and costs $s_t$. The algorithm must provide a pair of prices $(p,q)$ such that a sale happens if the buyer's value $b_t$ is less than $q$ and the seller's value is above $p$. The Gain from this trade assuming a sale happens is $(b_t - s_t)$.  The authors consider the problem of maximizing the gains from trade assuming either two bit feedback where we find out if $\\mathbb{1}[b_t \\leq q] $ and if $\\mathbb{1}[s_t \\geq p]$. They also consider the model where we have only one bit feedback where we know the product of these two bits of feedback. The original problem was already studied by Cesa-bianchi et al. This problem considers the setting where the buyer and seller have a hidden vector of preferences $\\theta_b, \\theta_s$ and their private values are generated from a shared context $b_t = x_t^T \\theta_b$ and $s_t = x_t^T \\theta_s$ . They consider where there may be some noise that is added as well as the budget balanced setting where the prices offered to both parties must be the same ($p=q$). \n\n\nThe main results:\n\n1) In the two feedback setting with strong budget balance $p=q$ at each time step when there is no noise in the setting. Here the authors use a natural modification of the feature based toolification.\n2) In the two bit feedback model with noise, where the noise is i.i.d coming from distributions with bounded support and densities. Finally they devise an algorithm following the explore-or-commit framework where the authors decompose the gain in terms \n3) They also study the one bit feedback problem where you only find out if a sale happens or not. To get good bounds for this model they assume they have a good regret for the strongly-balanced two bit feedback and then use that in a black box manner. However the new bounds only have a global budget balanced guarantee.", "questions": "1) I am wondering why the stronger bounds from Contextual Search (Liu et al) were not used in place of the Feature Based Pricing. It seems many of the ideas would carry over and you would achieve improved regret guarantees.\n\n2) It would be useful to know what new ideas are introduced for noisy setting  and how much was already known in other settings.", "limitations": "", "rating": 8, "confidence": 3, "soundness": 4, "presentation": 2, "contribution": 3, "strengths": "The authors propose a very reasonable contextual model of online bilateral trade. I find the new model to be well motivated and combines two natural areas of study namely bilateral trade and online contextual regret minimization. The algorithms themselves seem interesting and are fairly natural. \n\nThe reduction from the two bit strong budget balanced case to the one bit global budget balanced case is perhaps the most interesting to me. Essentially it is a general recipe where by one can exploit explore-or-commit algorithms and perform the explorations in such a way that we can always get feedback about either the buyer or seller. However, we may lose regret compared to other party, and thus we need to ensure that there is sufficient budget to do this. This is done by measuring the average profit the 2 bit algorithm can learn and then appropriately setting the parameters to balance out the findings.", "weaknesses": "Although the algorithms are natural and interesting, I am unable to distinguish where the new ideas are and how much of the paper is using known tools to a new setting. I would appreciate more explanation on what the new ideas are in both the two bit setting and the one-bit setting. \\o", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "X0mTOX0kgn", "reviewer": "Reviewer_Pddv", "summary": "In this paper, the authors investigate online contextual bilateral trade problem, where the valuations of two traders are modeled by different (unknown) linear functions. The authors focus on two different feedback models: (1) two-bit feedback model, where the learner can observe the binary feedback of both traders (2) one-bit feedback model, where the learner can only learns the binary information of whether the trade happens or not. For (1), the authors propose an online learning algorithm to set trading price at each round (that satisfies the strong budget balance constraint), which achieves $O(T^{2/3})$ regret. The authors also show a matching lower bound. For (2), the authors provide a reduction from one-bit feedback model to two-bit feedback model by sacrificing per-round budget balance to global budget balance and show the algorithm used in (1) can be applied to (2) and still achieves sublinear regret guarantee.", "questions": "1. Can you elaborate a bit more about the comparison with the related work, \"A contextual online learning\ntheory of brokerage. arXiv preprint arXiv:2407.01566, 2024\"? The setting is very similar, however, it seems the valuations of two traders in their paper share the same expected value.\n\n2. For the one-bit feedback model, if we want to maintain per-round budget balance, is it still learnable?", "limitations": "", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The paper is well-written and analyzes a very interesting theoretical problem. The authors did a good job to describe the problem and how the algorithm handles the challenges. \n\nThe theoretical guarantee of the paper is sound. The authors provide a complete story for the setting with two-bit feedback model. In addition, the reduction from one-bit to two-bit by sacrificing budget balance constraint is very interesting and elegant.", "weaknesses": "There is no matching lower bound for the one-bit feedback setting. I also have some questions regarding this setting.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "jXTOaCF4gj", "reviewer": "Reviewer_CL94", "summary": "This paper studies the bilateral trade model which involves the challenge of enabling transactions between a seller and a buyer who both hold private valuations for the item. This paper considers specifically the online scenario, where at each step there is a fresh seller and buyer entering the system and the pricing decisions for both parties must be made immediately without prior knowledge of their valuations. The paper further restricts to the contextual setting where the private valuations for the seller and buyer are linearly featured by a context. A two-bid feedback is considered where for both the seller and the buyer, it can be observed whether the posed price has exceeded its value or not. By further assuming a strong budget balance between the buyer and the seller, the paper is able to derive a $O(\\log T)$ regret. Without the budget balance conditions, the paper achieves a $O(T^{2/3})$ regret, which is minimax optimal. The paper further discusses the one-bit feedback and shows the potential to obtain a sub-linear regret.", "questions": "1. How do you check whether the strong budget balance condition holds or not?\n\n2. Could you please conduct numerical experiments to show the real performance? Also, what is the computation complexity of your algorithms.", "limitations": "", "rating": 6, "confidence": 3, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "1. The paper derives strong $O(\\log T)$ regret, though under stronger conditions.\n\n2. The paper derives $O(T^{2/3})$ regret upper bound for their algorithm and shows that there exists a matching lower bound.", "weaknesses": "1. The main results of the paper rely on the two-bid feedback setting, where both the seller and the buyer reveal to the decision maker whether they want to sell the product or buy the product. This is quite a strong condition, and the paper would benefit from a more detailed discussion on whether this condition happens or not in reality.\n\n2. Though the theoretical guarantee is provided, there are not numerical experiments in the paper showing the empirical performances. Also, the computation complexity of the proposed algorithms has not been discussed.\n\n3. The algorithmic idea and the proof technique mainly build upon the previous work Cohen et al. (2020) and it has not been discussed which part of the proof is novel.\n\n4. The $O(\\log T)$ regret depends on some strong conditions that are hard to justify in practice.\n\n5. The paper is overall theoretical and it is not clear how to apply their algorithm in practice.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "im283ZxLrk", "reviewer": "Reviewer_HHmH", "summary": "The authors study the feature based online bilateral trade problem. Here,  the buyer's valuations are given by a linear function. The seller's valuation is similar. In each round, the buyer and seller see a new context that along with their private parameter vector determines the parameterized part of the reward. The noisy version of the problem adds a i.i.d. random variable (not necessarily zero mean) with the parameterized reward.  The authors study the problem in both 2-bit and 1-bit feedback under strong and global budget balance constraints, respectively. For the deterministic version they adopt existing  EllipsoidPricing policy and show a log(T) regret bound. For the noisy, version they propose an Explore-or-Commit algorithm that achieves a $O(T^{3/4})$ regret, which is further improved to $O(T^{2/3})$ (which matches the lower bound). Some tradeoff between budget and regret is established for 1-bit feedback case.", "questions": "Two bit feedback:\n- Do we gain anything by removing the budget balance constraint in the two-bit feedback case (simplifying the algorithm maybe)?\n- Can the authors provide more intuition of how combining the ETC, and Scouting strategy works? (maybe along the line -> with $O(T^\\beta)$  exploration regret we reduce the 'Range of Delta_t' = $O(T^{-\\alpha})$ and then the Scouting results in $O(T^{2/3})$ regret)\n- As we do not rely on the exact reward feedback, will approximately linear reward functions work? \n\n\nOne bit feedback:\n- In the one-bit feedback case, is the knowledge of $\\alpha$ essential? \n- Can the authors discuss if the $\\alpha$ dependency a side effect of selecting the specific strategy of collecting the profit in the first phase? Can we improve/remove such dependency by adaptively collecting the budget or by leveraging improved exploration strategy?", "limitations": "", "rating": 8, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "- This work initiates the feature based online bilateral trade problem\n- With budget balance and two-bit feedback they establish a tight $O(T^{2/3})$ regret bound with by combining Scouting and Explore-or-Commit strategies. \n- They extend the results to the one-bit feedback setup while maintaining the regret guarantees under the budget balance constraint.", "weaknesses": "- See questions for more discussions around improving the paper, and my own curiosity.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Poster)