Revenue Maximization Under Sequential Price Competition Via The Estimation Of $s$-Concave Demand Functions
Authors: Daniele Bracale
Moulinath Banerjee
Yuekai Sun
Cong Shi
Venue: ICLR 2026 Poster (2026)
Keywords: Dynamic pricing
Nash Equilibrium
Nonlinear Demand Learning
Regret Analysis
Sequential Competition
Shape Constraints
Primary area: learning theory
TL;DR: No-regret convergence to Nash Equilibrium of price competition with non-linear unknown demands.

Abstract: We consider price competition among multiple sellers over a selling horizon of $T$ periods. In each period, sellers simultaneously offer their prices (which are made public) and subsequently observe their respective demand (not made public). The demand function of each seller depends on all sellers' prices through a private, unknown, and nonlinear relationship. We propose a dynamic pricing policy that uses semi-parametric least-squares estimation and show that when the sellers employ our policy, their prices converge at a rate of $O(T^{-1/7})$ to the Nash equilibrium prices that sellers would reach if they were fully informed. Each seller incurs a regret of $O(T^{5/7})$ relative to a dynamic benchmark policy. A theoretical contribution of our work is proving the existence of equilibrium under shape-constrained demand functions via the concept of $s$-concavity and establishing regret bounds of our proposed policy. Technically, we also establish new concentration results for the least squares estimator under shape constraints. Our findings offer significant insights into dynamic competition-aware pricing and contribute to the broader study of non-parametric learning in strategic decision-making.

Published as a conference paper at ICLR 2026
REVENUE MAXIMIZATION UNDER SEQUENTIAL PRICE COMPETITION VIA THE ESTIMATION OF S-CONCAVE DEMAND FUNCTIONS
Daniele Bracale 'Moulinath Banerjee & Yuekai Sun Department of Statistics University of Michigan Ann Arbor, MI, USA {dbracale, moulib, yuekai @umich. ch. edu
Cong Shi
Department of Management
University of Miami Miami, USA baagshi@bus miimimmm......mmmmmm.... edu
ABSTRACT
We consider price competition among multiple sellers over selling horizon of T periods. In each period, sellers simultaneously offer their prices (which are made public) and subsequently observe their respective demand (not made public). The demand function of each seller depends on all sellers' prices through a private, un- known, and nonlinear relationship. We propose dynamic pricing policy that uses cemi-parametric least-squares estimation and show that when the sellers employ our policy, their prices converge at rate of O(T-1/7) the Nash equilibrium prices that sellers would reach if they were fully informed. Each seller incurs a regret of 0(T"/7) relative to dynamic benchmark policy. A theoretical contribu- tion of our work is proving the existence of equilibrium under Shape-constrainee demand functions via the concept of s s-concavity and establishing regret bounds of our proposed policy. Technically, we also establish new concentration results for the least squares estimator under shape constraints. Our findings offer significant insights into dynamic competition-awant pricing and contribute to the broader study of non-parametric learning in strategic decision-makee making.
INTRODUCTION
Pricing plays central role in competitive markets, where firms continuously adjust prices in response to demand fluctuations and rival strategies. A major challenge in competition-awan pricing lies in inferring rivals' pricing behavior from limited observations (Li al., 2024). Firms cannot easily estimate price sensitivity through controlled experiments since competitors do not coordinate to hold prices constant while one firm tests different price values. Although existing sequential pricing algorithms yield low regret and converge toward a Nash Equilibrium (NE), they often rely on linear demand framework (Kirman, 1975; Li et al., 2024), or nonlinear approaches restricted to a fixed parametric family (Goyal et al., 2023), limiting applicability. Because nonlinear demand better reflects reality (Gallego et al., 2006; Wan et al., 2022: 2023), we adopt a flexible semiparametric model with unknown parametric and nonparametric components.
Over T periods, N sellers set prices simultaneously; each seller's demand depends both their own and rivals' prices, an effect amplified beyond lincarity. Sellers observe competitors' prices but not competitors' realized demand. For analysis, we assume that all sellers the same algorithm realistic simplification: for instance, Pri (2025) describes a pricing service used by numerous local hotels in Colorado. These hotels, while independently operated, utilize the same class of algorithmic tools provided by the platform to set their prices. Importantly, although they observe competitors' prices, they do not share underlying demand information with another,
assume in this work.
We design tuning-fie free pricing policy purely based on shape constrained estimation that (i) maximizes each seller's revenue and (ii) guarantees convergence to the NE, the pricing configuration that would arise under full information (iii) attains sublinear regret against a dynamic benchmark, defined the worst-case gap between seller's average revenue under our proposed pricing policy (where neither
"Reference author

---

Published as a conference paper at ICLR 2026
model parameters competitors' demands are known) and optimal policy in hindsight (which assumes fixed competitor prices and full knowledge of the demand model).
The Role of Shape Constraints in This Work. this paper, we assume that the mean demand for given the price vector (pt, P-+) (where p-, denots the competitors'
seller E [N] {1,2,.. ..... prices), follows a single index model of the form Ely.lp,, p-1] = ( + (%, p-+)), where the demand link function 4/; is assumed to be both monotone and s-concave ((:-) denotes the euclidean inner product) and 3 > O, which generalizes the linear demand setting in Li et al. (2024), where W linear (that is monotone and log-concave, i.e. s-concave with # = 0). Below, we summarize the motivation and relevance of these shape constraints, whose importance will become further evident throughout the paper.
,.,,, N.
Monotonicity aligns with economic intuition, where the standard form of demand is decreasing in the seller's 's own price (Li et al., 2024; Friesz et al., 2012; Kirman, 1975), and consequently, since 3 > 0, the functions f); must be increasing preserve decreasing demand with respect to pt. Indeed, in this case, 8,, [f Pt. p-:] < O.
The s-concavity assumption of i also arises naturally as a generalization of the commonly used log-concavity (recovered when s = 0), and plays crucial role in guaranteeing convergence anal- ysis towards equilibrium (see Section 3.1) We emphasize that 8-concavity, being higher-order smoothness constraint than monotonicity, drives the convergence rate results.
2 RELATED LITERATURE AND CONTRIBUTIONS
Sequential Price Competition with Demand I Learning. Classic price competition with known demand goes back to Cournot (1838); Bertrand (1883), with later variants including multinomial logit (Gallego et al., 2006; Aksoy-Pierss for mixed logit (Morrow & Skerlos, 2011), and multi-epoch competition (Gallego & Hu, 2014; Federgruen & Hu, 2015; Chen & Chen, 2021). However, over the last two decades, demand learning for competitive pricing has advanced substantially.
et al., 2013; Gallego & Wang, 2014), fixed-point methods
In this paper, we study sequential price competition with demand learning. Early work (Kirman, 1975) analyzed symmetric duopolies with linear demand. Li al. (2024) achieved optimal vT regret for asymmetric linear demand, (p) a; - B.p; + Σnfs ThjPy, with unknown sensitivities. However, nonlinear demand is more realistic and widely used (Gallego et al., 2006; Wan et al., 2022: 2023). For instance, Gallego et al. (2006) study (p) (p:)) E, a (py) + k) for known increasing a; and E (0, 1]. In contrast, we analyze an unknown monotone single-index model
(p(p) = v.(-3.pp + Ef Nspp)) = ().(O..)))
(1)
where 0, has -3, in coordinate and Ni elsewhere, and both 0, and di are unknown. This strictly generalizes Li et al. (2024): setting v. (u) = u + recovers their linear model.
Monotone Single-Indes Models. By Equation (1), we have N single-index models E(y: pp) (O, p)), i E N 21, ..... N, with unknown O; E R and unknown links v/. We assume sh; is nondecreasing, which makes demand X nonincreasing in its own price p,, standard assumption in the economics literature (Birge et al., 2024; Li al., 2024). Monotonicity also permits fully data-driven, tuning-free nonparametric estimators (Balabdaoui et al., 2019). The monotone SIM is identifiable under mild conditions: ||0:1|2 = 1, and p has a strictly positive density on its domain (see Balabdaoui et al. (2019, Prop. 5.))). Balabdaoui et al. (2019) also propose joint estimator (O,,, ).,.) with L error of order 1133 for ((,, ,)), and study the normalized linear estimator
0 nm
0 o.n E arg min En (vl (0, (0) - - p p= -
00....1a
which remains consistent under elliptically symmetric p (*) (Brillinger, 2012). In this work, also assume that (t) follows elliptically symmetric distribution during the exploration phase. However, for our purpose, an 1 convergence alone for ((O((..)) is insufficient establish a regret bound, but a uniform (supremum-norm) rate suffices and is derived in this paper.
Connection with NE, virtual valuation, and s-concavity. We propose a sequential price competi- tion online algorithm that provides sublinear regret. The first step achieve this goal is to establish
2

---

Published as a conference paper at ICLR 2026
the existence and uniqueness of a Nash Equilibrium p", which is the fixed point of an operator T (see Section 3.1 for more details). A necessary condition for its existence is that each seller's 's virtual valuation
pi(u) + v.(1)/(((m)
(3)
is increasing with derivative bounded below: (u) 2 C for some G; > 0 for all i E N. This mirrors the N = 1 literature (monopolistic setting) such Fan al. (2024); Chen & Farias (2018); Cole & Roughgarden (2014); Golrezaci et al. (2019); Javanmard (2017); Javanmard & Nazerzadeh (2019),
which often assume log-concavity of vù; and 1 1i (implying Q 2 1).
Our key observation links the NE and shape constraints follows: (.(()) C. iff is (c: 1)- concave (Proposition 3.5; see the section below for definition s-concavity), with log-concavity recovered as special case when c; 1. This connection allows to estimate vi; via nonparametric least squares under s-concavity yielding a fully data-driven, tuning-free estimation procedure.
s-Concavity. A technical contribution of this work is the study of the uniform rate of convergence of the -east-squares estimator of a unidimensional s-concave regression function. As defined in Han & Wellner (2016), a unidimensional function v 4 + (0, oo). U C IR, is said to be s-concave for some 8 E IR, and we write vo E Fx)) if & ((1 A)uo + Aun) 2 M2 (vb (wo) db (u1): A), for all
Mo. U1 E lI and X E (0, 1), where
((1 N) + AU1)
8 + 0, yo. V1 >
M2 81: A) &
0,
8 < 0, yo = y1 =
Vo
0.
This notion generalizes concavity (s 1) and log-concavity (which holds for = 0. in the sense that lim,-0 (yo. y1; A) = MMoo 3/; A)). These classes are nested since (24) c Fo(U)) c (,),,. if -00 r 0 < 00. The class of log-concave densities has been extensively studied: see Bobkov & Madiman (2011); Dümbgen & Rufibach (2009); Cule & Samworth (2010); Borzadaran & Borzadaran (2011) 1); Bagnoli & Bergstrom (2006); while Han & Wellner (2016); Doss & Wellner (2016); Chandrasekaran et al. (2009); Koenker Mizera (2010) deal with general s-concavity. is easy to see that such functions & have the form e ( for some concave function o if s > O, where x+ = max (0, x). th = e for some concave function o if s = O, and sb = (d+) for some convex function o if s < O. Then, has the following representation: vp ho & where & u R concave and
s 0, x E R s < 0, x < 0,
V log(v);
8 0,y > 0,
=
(-z)1/5
dx(v)
8 < 0,y > 0, (4)
8 > 0, x > 0,
8 > 0,y > 0.
Different from previous results, we study the convergence rate for the more general class Fn (see Appendix for details) that contains functions of the form &b = hoo : U - IR where h R - (0, 20) a known increasing function in C2 and ø + R is an unknown concave function. Specifically, we consider i.i.d. observations (U;, Yi) (U, Y) for i = 1,2,...,% where YI,..., Yn are noisy ly...,,, representations of the mean function (w) (Y u) h()o(u)) and U1 S U2 S U, are contained in 24 We study the uniform convergence rate of v... = o Rn. where On is the LSE
on E argmin concave E (Y: h (U.))²
The uniform convergence of &h to v/o plays crucial role in establishing the convergence of our proposed pricing strategy to the Nash Equilibrium, as we will see later in the paper.
2.1 SUMMARY OF KEY CONTRIBUTIONS
We now provide a summary of our key contributions.
A novel semiparametrie pricing policy for nonlinear mean demand. We extend the standard approach to estimating the mean demand function of a firm X₂(-) by introducing monotone single index model {x(p) (), p)), where 3 is increasing and s.-concave for some s; > -1, providing substantially more flexibility than previous parametric models (Li et al., 2024; Kachani
al., 2007; Gallego al., 2006).
3

---

Published as a conference paper at ICLR 2026
s-concave mean demand functions. In many existing works, necessary conditions for the existence of the NE are derived by assuming that the virtual valuation function defined in Equation (3) is increasing, often by invoking log-concavity of the mean demand function. We show how all such assumptions can be cast under the more general framework of s-concavity. This reformulation allows the development of fully data-driven, partmm---aatttr-freee algorithm using shape constraints.
Regret upper bound and convergence to equilibrium. We establish upper bound the total expected regret and analyze the convergence to the NE for a general exploration length of order T for E (0, 1) (Theorem 5.4). Our results reveal the existence of optimal choice of & that minimizes the total expected regret for each seller, leading to a regret of order (NN3/216/7) where O excludes log factors (Remark 5.6). Moreover, we show that by the end of the selling horizon, the joint prices set by sellers converge to Nash equilibrium prices at rate of ((N3/4T--17))
Concentration inequality for s-concave regression functions in the supremum norm, Our work involves establishing concentration inequality for the nonparametrie LSE, under the supremum norm, for a large class of shape constraints that includes s-concavity (Appendix H). As a minor contribution, we derive concentration inequality for the parametric component 0 of the monotone single index model (Proposition D.3), while previous results show convergence in probability or distribution (Balabdaoui et al., 2019).
General Notation. We use ||. 11, Il ll2 (or || ID-II Il for the L', Euclidean, and sup norms, respectively, and (u, v)= u for the inner product. The unit sphere in R. is SN--1 = {x E IR ||*|| = 1}. We write (-) to suppress logarithmic factors and use S to hide absolute constants. For functions, C (52) denotes m-times continuously differentiable f f Ω - R. A Lipschitz function has constant L,g > 0 with respect to prespecified norms. is a contraction if L < 1. If f (²)), Ω C R, it is μ-strongly convex if f"(x) 2 μ > O. Finally, following Delmas et al. (2024, Pag. 86), a random vector Z 6(m, A. has elliptically symmetric distribution with location m. scale matrix A > 0 (positive definite), and density generator [0, oc) + [0, oo), if (z) x ((2 - m) A - m)).
3 PROBLEM FORMULATION
We adopt problem setup similar that of Li et al. (2024). We consider N sellers, each selling single type of product with unlimited inventories over selling horizon of T periods. We use t e T & T
{1, , to index time periods and e / é {1, 21,2..... ... to index sellers. At the beginning of each period, each seller simultaneously selects their price. For seller i, i,
E P, - (p., Pol. denotes the price that seller offers in period t, with price bounds ps < P, and Pa.Ps [0, +00). Let
P A sEN))))))) denote the competitor prices at time f, p(()) & (D) )ēEN vector, and let P & IIEN [pt. p.). The vector p!* (f) is made public time then observed by all the sellers. A common knowledge is also the set
( denote the joint prices'
u 2 [-
Pmax: Pmma],
Pmax
-EiEN P2) 1/2
(5)
The demand 3/ (1) of seller in period is observed by seller i and is kept private, i.e., not shared among competitors. The individual demand ( depends on the offered prices of all sellers, ((0) P. and follows a nonlinear model:
w1ah (t) +((", (p & (=Bpp) + (7., "yr.p".)) (T))) (1). TET, (6)
JEET where {E(") JEET are (zero mean) o, p,-sub-gausse demand noises following independent and identical
distributions (e!") and e can be correlated with i + i,j E EV), and 0, is unknown vector of dimension N with i-th entry equal - and the remaining entries being the values of 7 E NN--1 ordered. The parameter vector 7/2 measures how seller i 's demand is affected by competitor prices. We assume that the parameter space is such that the average demand X; is non-negative and 0p A < among all values of (0,, Jie: a similar assumption is found in Birge et al. (2024); Li et al. (2024).
The above conditions hold vi, 1i. > 0 and 3. > O, which are explicitly assumed in Assumption 3.1.
Assumption 3.1. For every i E N,, th U + [Be B where: dh E C²( is unknown; 0 <
Bgg Bgg < 00 are known; 0 < Bgg S V/ S Byy and W < Bgg, where Buy, Buy, Bug 0
4

---

Published as a conference paper at ICLR 2026
necessarity known. We also assume
3 2 2.- 10.12 = B8 + 11 11, i.e. 0g E SN-11
where 3 E (0. is an unknown constant.
The constants B,, Be are known by the seller i (they are used to compute the optimization problem in (11)), however, firms can estimate them easily from historical sales data and operational capacity limits; moreover loose bounds suffice and do not affect the rates in Theorem 5.4. The condition ||0:122 = guarantees the differentiability of the monotone single index model (Chmielewski, 1981;
Balabdaoui et al., 2019). Note that Equation (6) is well defined, that is (0., (()) E U, indeed |00112 = = 10,, p) ||p||2 Pmax. Vp P. Regarding %/ while many applications assume Tiy > O, this restriction is not required for our algorithm or theoretical guarantees our results remain valid when 7ij > 0. We allow "hy be negative to capture settings with negative cross-effects, such as vertically differentiated products, where raising a competitor's s price may reduce my demand if consumers perceive their product as higher quality.
Individual Regret. (cumulative) revenue
Seller i N aims to design policy (p!") hET that maximizes their individual
(T( A E 11 =E
rev.(p.lp..) é p.che + (Y: P-.)). p p2)),
Maximizing a seller's revenue can be reframed as minimizing their regret. Each seller competes with dynamic optimal sequence of prices hindsight while assuming that the other sellers would not have responded differently if this sequence of prices had been offered. Under such dynamic benchmark, the objective of each seller E N minimize the following regret metric in hindsight:
Reg, (T) A EE rev,, rev, (p. | p [
RR(T), r,(p-:) E argmax reve(pi pp-)), PiEP,
(7)
where T, P- P, is denoted the i-th seller's Best Response Map, and p-1 & (p5)SEN((1)
Nash Equilibrium (NE). A Nash equilibrium p' = (pt))eN E P is defined as a price vector under which unilateral deviation is not profitable for any seller. Specifically,
(ev:(pt p=.)) 2 rev;(px p=+), Vp, E ei Vi (N),
or, equivalently, p is a solution to the following fixed point equation:
p" [(p") (Ti(p" (p'p" P.P
(8)
where I' is called Best Response Operator, and its components I'2 are defined in (7).
3.1 MAIN ASSUMPTIONS
Before presenting the main assumptions, clarify why framework requires two key properties: the best-response map must be contractive, and each seller's 's revenue function must be strongly concave. These conditions ensure well-posedness of the equilibrium and enable the stability and convergence guarantees developed later.
The objective of this paper is to design an algorithm that guarantees sublinear regret for every seller, i.., Reg, (T) = o(T) for every E A. Our policy consists of two phases: an exploration phase, in which each seller learns their individual best-response map I' by consistently estimating the parameters (0;, vbz), and an exploitation phase, in which, at each round f, seller sets their price according to p.
(t- D)) or equivalently (t) (t)(t)))). The link between regret and equilibrium is straightforward: the individual regret is controlled if the iterates converge to the NE, In
fact, Reg, (T) $ ("E) p² 1l were p* is a NE (see (37) for a detailed bound). By the triangle
inequality, have
- -(p"))rr(("'' Ip (+) - -p'l < - [||[+[[[((( - r(pp)))))))))) I | - -l Lr (1-))) - ppIl,
where Lr is the Lipschitz constant of I and || 00 supper |[([)]]] Therefore, convergence to p' requires two ingredients: (i) Contraction: < Lr which ensures that deviations from the
5

---

Published as a conference paper at ICLR 2026
NE shrink geometrically; (ti) Consistent estimation for ||T - which follows from consistent
estimation of (0,, th2) and strong concavity of rev;(- p-4) uniformly in p-i, for each seller E N. Putting these together, we obtain (see (39) for formal inequality):
Blpp (T) p'1 TT
(0) - -'ll + estimation error E r Illes
as T - oc.
(9)
shrinks under contraction
vanishes under strong concavity
Additionally, strong concavity ensures the existence of the NE, while the contraction property of the best response map implies the uniqueness of the NE.
Assumption 3.2. For every E NN, revi(- p-c) is strongly concuve in Ps. uniformly on p-; E P_;'.
By twice differentiability of thi Assumption 3.2 is guaranteed if μri - 23.Bw. B.p:Bog > 0.
Indeed, since by Assumption 3.1 | S Buy and of 2 Bog we have
- -6% rev.(p) p-.) 2 23, B M
== pi.
Assumption 3.2 guarantees that the best-response map r; in (7) is well defined for every p-;- More importantly, it guarantees the existence of the Nash equilibrium, in line with standard results in competitive games (Scutari et al., 2014; Li et al., 2024; Tsekrekos & Yannacopoulos, 2024). Instances where Assumption 3.2 is satisfied include linear demand models (Li et al., 2024), concave demand specifications, and a class of s,-concave demand functions with s; > -1, A more detailed discussion of these and further examples is provided in Appendix 1.1. The next result is an immediate consequence of Theorem 3, in Scutari et al. (2014).
Lemma 3.3 (Existence of NE). Under Assumptions (3.1) and (3.2), there exists a p* E P satisfying the fixed point equation in (8).
By Assumption 3.2, the map (p=:)) can be recovered by solving the first order conditions (FOCs), dg. rev; p-+) = 0. and projecting the solution onto P,, We now determine a shape constraint assumption that is sufficient to satisfy the FOCs. Specifically, we can show that I; can be written as (see the proof of Lemma 3.7 for the derivation)
(p(:)) si -/ss., gu(u) a uu pr (u)()) & u vx(n)/V((())
provided 92; exists. Here 1lp, is the projection into P, and y is called virtual valuation function of firm i. For this purpose, we introduce Assumption 3.4, which makes the spi' invertible.
Assumption 3.4. Vi E N, there exists constant c; 0, known to seller i, such that vp; 2 C..
Assumption 3.4 covers the linear demand model by Li et al. (2024) for which (b,(u) a; + t (u) 2u + a; = o 2 2 and can also be found in several works with N (monopolistic setting); for example, Assumption 2.1 in Fan et al. (2024), Assumption in Chen & Farias (2018), Equation in Cole & Roughgarden (2014) and Golrezaei et al. (2019); Javanmard (2017); Javanmard & Nazerzadeh (2019) which assume vh; and 1 v.. to be log-concave (which specifically implies e 2 1), where db; is a survival function.
We now present an equivalent formulation of Assumption 3.4 terms of s-concavity, condition that will allow us to estimate dh via shape constraints (the proof is provided in Appendix B). Examples of s-concave functions can be found in Appendix L.
Proposition 3.5. For every i N. of 2 c; if and only if v/ is (c; 1)-concave.
We now establish a sufficient condition under which the operator r (Ti)ve(N) is a contraction in P. Assumption 3.6. supseN l99/ll
Assumption 3.6 generalizes Assumption in Li et al. (2024) (in their case (u)
Og =
(u( = [u + a;)/2 + gf = 1/2. matching the contraction constant Lr in Equation 30 of their work). Similar assumptions are found Kachani al. (2007). The proof of the following result relegated to Appendix C. In practice, Assumption 3.6 states that the influence of competitors' prices on seller i's optimal response is sufficiently small relative to the sensitivity to its own price.
'This means that there exists & > 0 independent of p.; such that for all æ, E P; and all p- E P-u. ry p-:) - (x p-:) < 0 rew, (z p- x) & fly 11y-x1'" x01

---

Published as a conference paper at ICLR 2026
Lemma 3.7. Let Assumptions 3.2, 3.4 and 3.6 hold. Then, I (T DiEEIM P P is a contraction with contraction constant Ir == suPteN (illl// < 1. Consequently, the NE p" is unique.
Remark 3.8. In the specific case where the 4hs are 8i-concave for some 8, -1/2 (i.e. >> 1/2, which happens for example if the vo are log-concave, i.e. C; = 1, or concave, Le. Q = 2), then
s((w)) = = 1/4ll,, ((w) 2 1- 1/a > -1, g((u) = 1--1-110 1//11e, ((w) < 1, = 1 < 1.
In this case Assumption 3.6 reduces to 3r > I. but since 3, = (1- 1=111///2 the condition
becomes 11 + ll < 1. But since 11xl12 S 7/lla, sufficient condition is Iralla 1/v2.
4 PROPOSED ALGORITHM
Our Algorithm consists of an initial exploration phase for parameter estimation, followed by an exploitation phase where sellers set prices based on the learned demand model. In the exploration phase, each seller i E W samples prices p, exploration length is x T for some & E (0, 1), to specified later (Remark 5.6).
(t) from a distribution Z; for = 1,,,, ...,.. The common
Remark 4.1 (The common exploration phase). See Appendix 1.2 for clear discussion of why sellers have no incentive to alter the exploration phase.
(t) charged by different sellers in the exploration phase not necessarily The random prices Pi
independent, and we will use 2 from now on to denote the joint distribution of the price vector the exploration phase. Recall that at every time I, each firm i observes their own (random) demand value .....PX) (())T are made public. At the end of the exploration phase, firm estimates (0,, the) using data {(p(),
( while the prices (t)) = (p(")
(1) (0 ))))rr More precisely, each firm chooses proportion of initial data points in the exploration phase T(()) = (1,2.... } to estimate 0,, and subsequent time points ((22) {N&T + 1............ ..,,, T} estimate 14, For simplicity of notation we define n;
(1) | TK; and (2) |T.21 r(1 k.))
Remark 4.2 (Need for two different phases for model estimation). Owing space constraints, defer to Appendix I.3.
Remark 4.3 (Selection of 7 and K2). For every seller i E N, the parameter K; can be chosen to minimize that seller's 's total expected regret. By Theorem 5.4 there is unique optimum, denoted K. = K (N,T) E (0,1) that is characterized by Equation (14). Choosing K; <; improves only unchanged. For the exploration horizon T we set x T for some & O. Remark 5.6 argues that 5" 5/7 is the unique value that minimizes the total expected regret across all sellers. These values nς and t are "optimal" only in the sense that they aim to minimize the regret constant and the exponent Tf respectively within our derived upper bound; we do not claim minimax optimality of the regret rate itself.
the leading constant of the regret but leaves the convergence
(1) Exploration phase part 1: T(()) Each seller estimates
(-) = 0, 8./110.ll.. where
0, = argmin BERN
()) A EI (v." (0.p()) - -)))] p == > "0 / (10)
(2) Exploration phase part 2: T:(2) Each seller i defines w. (4) e (0,, (0) for l T( (note that
w ld because 00:12 1, where 2 is defined in (5)) and the estimator v = h., P.
where = (known by Assumption 3.4), and
क, E argminsEH, Ever, (3 he, (o(
(11)
where ha, is defined in (4). The class H. consists of all functions &i : 21 - [B,, Bo,] that are both monotone non-decreasing and concave. The bounds B., and BB, are chosen so that [B a B hg (lB Bs, and are therefore known, indeed B B By, (defined in Assumption 3.1) are known. A detailed justification of this estimator in (11) is provided in Appendix D.2.
7

---

Published as a conference paper at ICLR 2026
At the end of the exploration phase, seller obtains estimator of their revenue function:
rev; [=; -=:11) _ p. (-B.p; + (3h, --; 1),, Vpu E Pi.
(12)
where p _ (1-1) the prices of all the other firms at time 1, that are made public. A price p; is then offered by firm as maximizer of (12) over P.. We present the full procedure in Algorithm and a visual representation of the exploration cepatioonexpliiaationn scheme in Figure in Appendix summary of the information available to each seller to run Algorithm can be found in Appendix A.
(c)
Algorithm SPE-BR (Sami-Parametric Estimation then Best-Response)
Input: the (joint) distributions of the exploration phase 2.
Output: Price p!d that seller i A offers in period T _ . for t S T do
Sample p( = (Pi P2
(t) (0)
.P2) ~ 2, and let y/ denote seller i's demand as in (6).
end for
Each seller E N constructs an estimator (0 1 (-) using data {(p!)) (0) 1. as
defined in (10) and (11)
T 2,
(1) Each seller i E A offers price p = argmax prU, ,, (- + ( "
(2) After all prices have been posted, each seller observes their demand y; as in (6).
end for
REGRET ANALYSIS
We begin by analyzing, for each seller E A,, the convergence of 0, and V. from the exploration phase. An informal overview is given in Section 5.1, while formal results appear in Appendix D Appendix D.I for 0, and Appendix D.2 for U ". We then study NE convergence and the regret bound in Section 5.2.
5.1 ESTIMATION OF THE MODEL PARAMETERS
In the single-indes setting, the linear estimator in (10) attains a vn rate when covariates (here, joint prices (()) are elliptically distributed (Balabdaoui et al., 2019; Brillinger, 2012). We impose this elliptical law during exploration to ensure consistency and, unlike prior work, derive concentration inequality for (10) (Proposition D.3), which underpins our regret bound.
Assumption 5.1. = 6 (m, A.g) with Cmin Il < A < Cmax for some 0 < Gmin < Cmax < oc, and g satisfying (1r y) ( for all z, 0.
Assumption 5.1 covers Gaussian and, more generally, elliptically symmetric laws with g(x) a- (a > 0, > 0). This yields aub-Gaussian samples, crucial for the concentration result in Proposi- tion D.3. We defer Remark D.I and Remark D.2 for detailed motivation on Assumption 5.1.
Proposition 5.2 (Informal version of Proposition D.3). Under Assumptions 3.1 and 5.1, ||0. 0,112 = O( log ! "////""))))))/ (122))
Theorem 5.3 (Informal version of Theorem D.6). Let Assumptions 3.1, 3.4 and 5.1 hold. Then, for every compact K CU we have E|suppeR 1 (u) via (w)]] ((
5.2 CONVERGENCE TO NASH EQUILIBRIUM AND INDIVIDUAL REGRET BOUNDS.
We now ready to prove main result for fixed value & E (0, which, recall, represents the proportion of (common) exploration length x T
Theorem 5.4. Suppose that Assumptions 3.1, 3.2, 3.4, 3.6 and 5.1 hold. Then, Algorithm produces policy such that, for each i E N:
(1) Individual sub-linear regret: Reg, (T) O(TS + 2 2//2 ( T)//
8

---

Published as a conference paper at ICLR 2026
(2) Convergence to NE: E [|p(T] -p" TT (log More precisely, we have
Bilp (0) - -D" - N 26/5 (log 7)
8/5 + 1 1)
1
(13)
Moreover, for each i E N,, there exists unique x.j E (0, 1) that minimizes the seller's i regret, and satisfies the implicit equation:
46,,1/10 x/22 5. (1x)/7//
(14)
where B. and '6; are defined in (17) and (21), respectively.
Remark 5.5. Since 64 and B, depend on unknown quantities, it is typically difficult for seller to compute K4 exactly. However, any positive choice of 6; and 9, guarantees K₃ (0,1), while the regret and NE convergence rates remain unaffected, with only the leading constants changing.
Remark 5.6 (Optimal value of & and comparison with monopolistic results). By Theorem 5.4, the value of E that minimizes the expected regrets Reg,(T) (T)) is the value that equalizes the exponents of in the regret upper bound: T + T (ignoring logarithmic factors). This yields = 5/7. Consequently, with this choice E, have that for each i N
Reg, (T) = (NN9/777/ (logT) T)))), and
EIIp (T)
p (T) -p'
For N = (i.e. in a monopolistic setting), our regret upper bound matches that of Fan et al. (2024), who estimate the link function via a kernel-based method. Their result is stated for binary outcomes ya. whereas our framework accommodates continuous ys: nevertheless, our estimation procedure can be straighiforwardly adapted to the binary-response setting, yielding the same regret rate as in the continuous case, Moreover, relative to the kernel approach in Fan et al. (2024), our method offers the advantage that is fully data-driven and requires no bandwidth selection.
Remark 5.7 (Mispecifying $;). As established in Remark G.3, if the sellers choose parameters s S 8; satisfying sup:ex [1 < 1, then the convergence rates of the regret and the NE are preserved. This phenomenon is also confirmed empirically in Section 6.
Remark 5.8 (Algorithmic collusion). Our results indicate that when all sellers employ the same class of learning algorithu that we propose, the dynamics do not give rise to collusive behavior: the learning process converges to the pure Nash equilibrium, and prices do not drift upward coordinated way. This is beneficial from consumer perspective, as it prevents the emergence of price increase. However, if some sellers deviate and adopt different algorithms or learning rules, then the interaction dynamics may create conditions under which algorithmic collusion can emerge.
NUMERICAL EXPERIMENTS
We evaluate the performance of Algorithm in markets with N E {2,4, 2,,4,,, 63 sellers. A detailed description of the simulation setup is provided in Appendix J; here we present the main setup together with a discussion of the results. For each seller i E N = (1,2...., NY. the price vector (() is supported on P = [0, 1,,3]xN For every N, we examine the convergence behavior as the contraction constant Lr varies specifically, when Lr x 0, Lr s 0.5, and Lr s 1. The link functions are O-concave and their price sensitivities are generated such that 0 = (-B,, has unitary - and satisfies Assumption 3.6. A fixed point exists and is unique by Lemma 3.7 and is recovered using a simple root-finding algorithm. The demand noise of each firm follows a uniform distribution [-0.05, 0.05). For every T E [100, 400, 800, 1600, 3200]. we apply Algorithm 1. We independently repeat the simulation 30 times to obtain average performances and 95% of confidence intervals. In Figure 5 and Figure 6 we summarize the results. The panels show: (i) the convergence of the estimators 0 and uhg (ii) convergence of prices to the Nash equilibrium p and the expected cumulative regret plotted on log-log axes (with fitted slopes) to reveal the empirical rate. Across runs, the observed rates are consistently faster - i.e., exhibit smaller slopes than the theoretical upper bound. Regarding the minimization problem in (11) under the class of monotone increasing and s-concave functions, we note that designing efficient algorithms specifically tailored to s-concavity remains an open and largely unexplored area. Nonetheless, in this work, we leverage a fast optimization solver to approximate the solution. Additionally, in Appendix J.2 provide simulations under different exploration phases across the sellers and in Appendix J.3 simulations showing how mispecifying s; affects the regret and NE convergence rates.

---

Published as a conference paper at ICLR 2026
7 FUTURE RESEARCH DIRECTIONS.
There several promising directions for future research. One is design an algorithm allowing each seller to independently set their exploration length, which not permitted in our setting as outlined in Remark 4.1. For this purpose, key theoretical goal is to obtain uniform convergence for the joint estimator (0,, 4/2). While this would not change regrets or NE rates (it will only improve constants), it could yield practical gains: currently, 0g uses K,7 samples and 4 the remaining (1 Kz)T, whereas joint estimator would leverage the full т. Existing results are limited: Balabdaoui et al. (2019) shows only L convergence under monotonicity (we additionally require s,-concavity), and Kuchibhotla et al. (2021) provides uniform convergence under convexity/concavity (s; = 1) with only Op rates. Our setting instead calls for non-asymptotic supremum- concentration for the joint estimator, ie., tail bounds in (52).
Another challenge is estimating the s; 's themselves. While we assume them to be known, in practice, this may not be the case, and developing a theory for this harder setting remains to be explored.
Finally, ambitious direction is to design algorithms that bypass the classic exploration-exploitation trade-off. Here, each seller i would use the entire history of public prices and private demands {(p)), "v((") Jests ensuring (T) NE T + co. The main challenge is avoiding incomplete learning (Keskin & Zeevi, 2018), which can yield poor parameter estimates and higher regrets.
REPRODUCIBILITY STATEMENT
In the Supplementary Materials, we provide zip archive with all the code required to reproduce the results and figures in this paper. The archive contains three top-level folders whose names match the corresponding figure labels in the PDF. Inside each folder, we include Python notebooks with step-by-step instructions that describe how to run the experiments and regenerate the figure. Running the notebooks as instructed will recreate the plots and save them to the corresponding folders' directory named "PLOTS".
DETAILS OF LLM USAGE
We used generative AI tools when preparing the manuscript to polish our sentences and correct potential typos; remain responsible for all opinions, findings, and conclusions or recommendations expressed in the paper.
REFERENCES
Pricingservice.ai. https://www http://wwwwwiiiie.eeweeeeo ai/, 2025.
Accessed: 2025-07-26.
Al-powered room pricing & revenue management solution for hotels. Founded 2021 in Boul- der, Colorado.
Margaret Aksoy- PissssPi Gad Allon, and Awi Federgruen. Price competition under mixed multino- mial logit demand functions. Management Science, 187711887 2013.
Mark Bagnoli and Ted Bergstrom. Log-concave probability and its applications. In Rationality and Equilibrium: A Symposium Honor of Marcel K. Richter, pp. 217-241. Springer, 2006.
Fadoua Balabdaoui, Cécile Durot, and Hanna Jankowski. Least squares estimation in the monotone single index model. Bernoulli, 25(4B):3376-3310, 2019.
Joseph Bertrand. Review of "theorie mathematique de la richesse sociale" and of "recherches sur les principles mathematiques de theorie des richesses.". Journal de savants, 67:499, 1883.
John R Birge, Hongfan Chen, N Bora Keskin, and Amy Ward. To interfere not to interfere: Infor- mation revelation and price-setting incentives in a multiagent learning environment. Operations Research, 2024.
Sergey Bobkov and Mokshay Madiman. Concentration of the information in data with log-concave distributions. The Annals of Probability, 3988) 201
10

---

Published as a conference paper at ICLR 2026
GR Mohtashami Borzadaran and HA Mohtashami Borzadaran. Log-concavity property for some well-known distributions. Surveys in Mathematics and its Applications, 1:203-219, 2011.
David R Brillinger. A generalized linear model with "gaussian" regressor variables. Selected Works of David Brillinger, pp. 589-606, 2012.
Karthekeyan Chandrasekaran, Amit Deshpande, and Santosh Vempala. Sampling s-concave functions: The limit of convexity based isoperimetry. International Workshop on Approximation Algorithms for Combinatorial Optimization, pp. 420-433. Springer, 2009.
Ningyuan Chen and Ying-Ju Chen. Duopoly competition with network effects discrete choice models. Operations Research, 69(2):545-55) 2021.
Yiwei Chen and Vivek Farias. Robust dynamic pricing with strategic customers. Mathematics of Operations Research, 43(4):1119-1144 2018.
Margaret Ann Chmielewski. Elliptically symmetric distributions: A review and bibliography. Inter- national Statistical Review/Revue Internationale de Statistique, pp. 67-74, 1981.
Richard Cole and Tim Roughgarden. The sample complexity of revenue maximization. In Proceedings of the forty-sixth annual ACM symposium on Theory of computing, pp. 243-252, 2014.
AA Cournot. Recherches sur les principes mathématiques de la théoric des richesses par augustin cournot (paris, france: chez hachette). 1838.
Madeleine Cule and Richard Samworth. Theoretical properties of the log-concaye maximum like- lihood estimator of multidimensional density. Electronic Journal of Statistics, 4:254-270, 2010.
Jean-Pierre Delmas, Mohammed Nabil El Korso, Stefano Fortunati, and Frédéric Pascal. Elliptically symmetric distributions in signal processing and machine learning. Springer, 2024.
Charles Doss and Jon Wellner. Global rates of convergence of the mles of log-concave and s-concave densities. Annals of statistics, 44(3):954, 2016.
Lutz Dümbgen and Kaspar Rufibach. Maximum likelihood estimation of log-concave density and its distribution function: Basic properties and uniform consistency. Bernoulli, 15(1):40-68, 2009.
Lutz Dümbgen, Sandra Freitag, and Geurt Jongbloed. Consistency of concave regression with application to current-status data. Mathematical methods of statistics, 13:69-81, 2004.
Jianqing Fan, Yongyi Guo, and Mengxin Yu. Policy optimization using semiparametric models for dynamic pricing. Journal of the American Statistical Association, 119(545):552-564 2024.
Awi Federgruen and Ming Hu. Multi Multi-product price and assortment competition. Operations Research, 63(3):572-584, 2015.
Terry L Friesz, Changhyun Kwon, Tae Il Kim, Lifan Fan, and Tao Yao. Competitive robust dynamic pricing in continuous time with fixed inventories. arXiv preprint /208. 2012.
Guillermo Gallego and Ming Hu. Dynamic pricing of perishable assets under competition. Manage- ment Science, 1245):1241-1223 2014.
Guillermo Gallego and Ruxian Wang. Multiproduct price optimization and competition under the nested logit model with product-differentiated price sensitivities. Operations Research, 62(2): 450-461, 2014.
Guillermo Gallego, Woonghee Tim Huh, Wanmo Kang, and Robert Phillips. Price competition with the attraction demand model: Existence of unique equilibrium and its stability. Manufacturing & Service Operations Management, 8(4):3993375. 2006.
Negin Golrezaei, Adel Javanmard, and Vahab Mirrokni. Dynamic incentive-aware learning: Robust pricing in contextual auctions. Advances in Neural Information Processing Systems, 32, 2019.

---

Published as a conference paper at ICLR 2026
Vineet Goyal, Shukai Li, and Sanjay Mehrotra. Learning to price under competition for multinomial logit demand. Available at SSRN 4572453, 2023.
Piet Groeneboom and Kim Hendrickx. Current status linear regression. The Annals of Statistics, 46 (4):1415-1444, 2018.
Qiyang Han and Jon A Wellner. Approximation and estimation of s-concave densities via rényi divergences. Annals of statistics, 44(3):1332, 2016.
Adel Javanmard. Perishability of data: dynamic pricing under surying-cocfficinn models. Journal of Machine Learning Research, 18(53):1-31, 2017.
Adel Javanmard and Hamid Nazerzadeh. Dynamic pricing in high-dimensions. Journal of Machine Learning Research, 20(9): 2019.
Soulaymane Kachani, Georgia Perakis, and Carine Simon. Modeling the transient nature dynamic pricing with demand learning in a competitive environment. Network science, nonlinear science and infrastructure systems, pp. 223-267, 2007.
Bora Keskin and Assaf Zeevi. On incomplete learning and certainty-cquivallnnce control. Opera- fions Research, 66(4):1136-116)) 2018.
Alan P Kirman. Learning by firms about demand conditions. In Adaptive economic models, pp- 137-156. Elsevier, 1975.
Roger Koenker and Ivan Mizera. Quasi-concave density estimation. 2010.
Arun K Kuchibhotla, Rohit K Patra, and Bodhisattva Sen. Semiparametric efficiency in convexity constrained single-index model. Journal of the American Statistical Association, pp. 1-15, 2021.
Ker-Chau Li. Sliced inverse regression for dimension reduction. Journal of the American Statistical Association, 86(414):316-33) 327,7, 1991.
Shukai Li, Cong Shi, and Sanjay Mehrotra. LEGO:
Optimal online learning under sequential price competition. Major Revision at Operations Research. Available at SSRN 4803002, 2024.
Yiyun Luo, Will Wei Sun, and Yufeng Liu. Distribution-frie contextual dynamic pricing. Mathematics of Operations Research, 49(1):599-618, 2024.
W Ross Morrow and Steven J Skerlos. Fixed- Fixed-point approaches to computing bertrand nash equilib- rium prices under mixed-logit demand. Operations research, 59(2):328-33 0008834552040 2011.
Alexandre Mösching and Lutz Dümbben. Monotone least squares and isotonic quantiles. 2020.
Constantin Niculescu and Lars-Erik Persson. Convet and their applications, volume 23. Springer, 2006.
Gesualdo Scutari, Francisco Facchinei, Jong-Shi Pang, and Daniel P Palomar. Real and complex
monotone communication games. IEEE Transactions on Information Theory, 60(7):4197-4231 2014.
Andrianos E Tsekrekos and Athanasios N Yannacopoulos. Variational Inequalities in Management Science and Finance. Springer, 2024.
Roman Vershynin. Introduction to the non-asymptotic analysis of random matrices. arXiv preprint arXiv:1011.3027, 2010.
Yi Wan, Tom Kober, and Martin Densing. Nonlinear inverse demand curves in electricity market modeling, Energy Economics, 107:105809, 2022.
Yi Wan, Tom Kober, Tilman Schildhauer, Thomas J Schmidt, Russell McKenna, and Martin Densing. Conditions for profitable operation of p2x energy hubs to meet local demand with energy market access. Advances in Applied Energy. 10:100127, 2023.
12

---

Published as a conference paper at ICLR 2026
APPENDIX
APPENDIX CONTENTS
(A) Summary of individual information
(B) Proof of Proposition 3.5
(C) Proof of Lemma 3.7
(D) Formal estimation of the model parameters Section 5.1
(E) Proof of Proposition D.3
(F) Proof of Proposition D.4
(G) Proof of Theorem 5.4
(H) NPLS for s-concave regression
(H.1) Technical Lemma
(H.2) Technical Lemma 2
(H.3) Proof of Theorem H.5
(I) Remarks
(I.1) Remark on Assumption 3.2
(I.2) Remark 4.1 on the common exploration phase
(I.3) Remark 4.2 on the need for two different phases for model estimation
(J) Simulations
KK) Additional Figures
(L) Examples of s-concave non-decreasing functions
A SUMMARY OF INDIVIDUAL INFORMATION
In this section, we summarize the information each seller must know to implement Algorithm 1.
Table Values known by seller i E
Known (or observed if specified)
Description
T
Time horizon
y: (observed)
Demand realization of seller Competitors' prices
p - (observed)
Prl
Price domain of seller i
41 Pmax: Pmax
Domain of 4/ 2 B v. B
B ., B
Range of 1/4
B B
G (or equivalenty 8; 1)
C;: lower bound of pp 8ş2 concavity parameter of dh. Joint price distribution during exploration
Length of the common exploration phase
13

---

Published as a conference paper at ICLR 2026
Table 2: Values unknown by seller E /V
Unknown (or unobserved specified)
Description
(0,, 1a)
Semi-parametto population parameter
2,
Lower bound of the price sensitivity 3;
4-1 (unobserved)
Demand realization of the i-th competitors
0,
Variance of the i-th demand noise &; Price domains of the i-th competitors
P-; = Pp)
Buy Byy
Lower and upper bound of vi
Byy
Upper bound of [e("]
{[B Buyl1istt
Ranges of i-th competitors demands (Wahiss Lower bounds competitors {pfts
B PROOF OF PROPOSITION 3.5
Recall the definition
pi(u) = =u vv((u)
vu(")) u NEU.
We have & 1+ W.
V.-ud" (eg) 2 a iff di vit +(: (8a- 1)( with 8; =
(#))
The statement follows by Lemma B.I.
Lemma B.1. Let be positive function defined in an interval (a, b) that is twice continuously differentiable. Then vb is s-concave iff sb v² + - 1)(w/)² & 0 in (a, b).
Proof of Lemma B.I. As s = 0 is a known result, we prove it for + O. A function & is s-concave and only if dg & is concave, where d, defined in (4). Then 3 is s-concave if and only if
df duz
d du (w) = |s] (6) (u) + (s ()) S o, u (a, b).
do(())
(2)
C PROOF OF LEMMA 3.7
We first find an analytic form of [p(p).). We have
(p) (p.))))) (c(p) = -.pp + 7/ P-+-
First note that, by strong concavity of p; - rev; l pp;) (see Assumption 3.2), the best response map is the projection onto P. or the value pt that solves the first order condition. More specifically
r.(p",) = p,,
where IIp is the projection into P; and of solves the first order condition of (8), that
θ
rev, (pvl(p)pp.)) =0
(15)
ap.
where we that rev;(p:/p-.)) p. Solving Equation (15) we have
(,(((p))) - -3.t = < Art (p'()) = 0
(p'))
Assumption 0:(p') -ن (7/ pi.) + pi (0(p")) 7/ p"
+ = * p - 1 p²;))
B
$ P. 9. p
B
14

---

Published as a conference paper at ICLR 2026
Thus
Tx(p',) = -II, gi gi(T p=.))
(16)
B,
We now compute an upper bound of the Lipschitz constant of the Best Response Operator r - iewr on the compact space P. This will allow us ensure contractiveness when this constant strictly less than For any p. P, have
| (p) I( = sup rT(p-;) - rr:p'':]
i&N
9:(7% p-i) - -9: p'..)
sup e.
Br
x sup
|g// 1%/ p-i - -.:---10 p'
Ke 9
S sup
| Yellillp-s -P'-ilo0
ieN B
11
I |pp plll sup
iEN
B,
= Lr pp - p' 1l:o
where
| = sup lgs (v)l VVV
V V v (1(())
In the second inequality, we used the contraction property of the projection operator, and where
l/illa
Lr - sup |1
sEN
which is strictly less than by Assumption 3.6.
D FORMAL ESTIMATION OF THE MODEL PARAMETERS IN SECTION 5.1
In this section, we formally explain the estimation procedure of the model parameters (0;, thx), for i N.
D.1 ESTIMATION OF THE PARAMETRIC COMPONENT.
In a single-index model, the linear estimator in (10) converges to the true 0, at a vn rate provided that the covariates (in this case, the joint prices (*) follow an elliptical distribution (Balabdaoui al., 2019; Brillinger, 2012). We adopt the same elliptical assumption on the (joint) distribution of the prices during exploration, to ensure the consistency of the estimator (10). In contrast to earlier work, establish concentration inequality for this estimator (Proposition D.3), which serves key tool in deriving our regret upper bound.
More specifically, in Assumption 5.1 we assume that D 6 6(m, A, g). where Cmia < A & CmaxI for some 0 < Cmin Cmax and the density generator is such that g(x y) g(z)g(v) for all r, 2 0, i.e.
(p(P) x g((p- (((p-))TAN -
Remark D.I. It should be noted that from a purely theoretical standpoint, we do not restrict the domain of the price vector p in the exploration phase to P. but this has essentially no implication for the application of the pricing algorithm in practice. To ensure that the i'th seller's 's exploration prices can, realistically, never lie outside P, [pt, p.), all they need take be a normal distribution (for example) centered at the midpoint of this interval with variance of taken to be an adequately small fraction of the length P, If the sellers function independently. as is generally the case, the joint distribution is certainly elliptically symmetric. More generally, view the parameters m, and g concentrating the mass of ② in with overwhelmingly high probability. Theoretically, some
15

---

Published as a conference paper at ICLR 2026
proposed price in many thousands of time steps could lie outside P, but realistically. the procedure entails no financial consequence for them. Letting D belong to an infinitely supported elliptical distribution allows the implementation of simple consistent linear regression-bans -aaoodd estimation to learn 0g which satisfies the concentration inequality proved in Proposition D.3 below, and is also important for certain conditioning arguments involved in estimating appropriate surrogates for the in the following subsection, while compromising nothing in terms of the core conceptual underpinnings of the problem.
Remark D.2. Assumption 5.1 holds for a wide range of distributions, including Gaussian distributions and, more generally, all elliptically symmetric distributions for which g(æ) = a a-n for a. 0 and > O. Before describing Assumption 5. we emphasize that selecting an appropriate distribution for the design points (here, the exploration prices) standard in inttoratioo-eplloiatati algorithms. This choice is crucial because it ensures that the learner can perform exploration design and obtain a consistent estimator. For example, both Fan et al. (2024) and Luo et al. (2024) employ uniformly randomized prices precisely to guarantee consistency of their estimators. We now describe the components of Assumption 5.1:
1. The requirement that exploration prices follow elliptically symmetric distribution is used to guarantee the consistency of the estimator of 0; in the single-index model. In particular, this assumption is invoked in Lemma E.2 to derive the normal equations (the same assumption can be found in Balabdaoui et al. (2019) and Brillinger (2012)). If the exploration distribution were not elliptically symmetric, the resulting estimator could fail to be consistent.
2. As will discuss in Appendix D.2, the property that g(x + g(x)g(v) (satisfied, for example, by Gaussian distributions) supports the estimation of the. It ensures that 4)s.0 (u) (defined in (18)) depends u solely through the argument of th rather than that of (see Equation (29)). This decoupling guarantees that th inherits key properties from th such as smoothness and adherence to the prescribed shape constraints, as highlighted in Proposition D.4. In turn, these properties are crucial for establishing consistency of the estimator of 12.-
We denote
== =ar(p))
which is proportional to A. Then, there exists < Smin < oo such that Smin & E. These constants will appear in Proposition D.3, which proof is provided in Appendix E.
Proposition D.3. Under Assumption 3.1 and Assumption 5.I, there exist a positive constant c (that
depend solely on the variance proxy a₂ of the sub-Gaussian random variable x (() (()) -p) p)ssschh
(1) sufficiently large, with probability at least 1 2 S n /16 that, for n.
n o0 the estimator in
2_
(10) satisfies
|0 0:112 S Bi
Nlogn!
(1]
where
2, = 4v2 Tx (2.0 +o..)
(17)
Aismin
where >; (ov(V=(0]x)) x)) var(0,'
for x (1() = =p()) -p and oy the variance proxy of the the Sab-Gaussian random variables y
D.2 ESTIMATION OF THE LINK FUNCTION VIA S-CONCAVITY.
This section provides uniform convergence result of oh, to sh, for any fixed 0 E S 1. In this section, all the results must be considered as conditioned on 0 = 0, estimated using data in T independent of data in T,(2), For simplicity notation, we re-index T:(2) as [n] {1, 2, ......... n2.. To estimate th we would need to know 0, in advance, indeed we remind that E(y;" (1) d (0,, (t)p(())) ())). However, our knowledge is limited approximation 0 of 0, and the observable
design points are w. (6, (1)). Note that
! E EU
16

---

Published as a conference paper at ICLR 2026
because ||0:1|2 = 1 implies Iw; (0;"1 < || S Pmaxx This implies that, with data {(uc} (0) ( de(m) we are only able to estimate
Mi )
(r a Ely,
w = u), u E.U.
(18)
We now construct an estimator of v4.0 and establish, in Theorem D.6, a uniform convergence result over any bounded subset K C U (where U is defined in (5)). Our approach draws on techniques from Mösching & Dümbgen (2020); Dümbben et al. (2004), which study uniform convergence in the context of shape-constrained estimation. A key assumption in these works one that does not require smoothness of the unknown nonparametric function
that the density of the design points, fic
is bounded away from zero on U. This ensures that the design points (5) E li are asymptotically dense within every subinterval of U, which in turn is sufficient for establishing uniform convergence of the estimator on such intervals. In our setting, fw is supported on all of E, and thus it is bounded away from zero on any bounded set K. Consequently, the uniform convergence result applies to any bounded subset K Cu.
Before establishing the convergence result, we must first characterize the shape constraints satisfied by the family of functions (-), 0 E 3 In Proposition D.4 (with proof deferred to Appendix F), we derive a closed-form expression for 4h (-) and show that both the monotonicity and the 8; C: 1-concavity of the original function 4// are preserved by vi uniformly over 0 E SN-1-
Proposition D.4. Under Assumption 3.1 and Assumption 5.1 we have the following properties:
(1) vi) = fgx-1 vb (10,, m.) + + Aa) ğ(a))a, u E R. 0 E S where
m. m + AO (u (0, m))
g(a)= olllalll//gex
ATA
and A is such that AAT = A.
(2) vi.00 E (2) and 0 < Bs. S vii Beg uniformly in 0 SN-1-
(3) (ss(u) (u)) x | 0.112 for all u E U and I SN-1-
(4) thio is monotone increasing in U for all 0 such that ||0 0:112
0 A0: Moreover W is Cmnax
bounded uniformly in S and there exists L > 0 independent of 0, such that (
( S L/u for all u, v E Ud, E Sx-1-
(5) If also Assumption 3.4 holds (i.e. 1h; is sc-concave for some 8; -1 as arises from Proposi- lion 3.5) then th is s,cconcave for any 0 E &SN-1-
By definition of s-concavity, from point (5) in Proposition D.4 we have that for every 0 E Sx-1 there exists a concave function 6i,e that vi = ht, o 6i.0. where ha is defined in (4), and 8; = is known by Assumption 3.4. We could then estimate Φi using LSE under concavity restriction, that is
T E argmin pes,
Σ (1) - lis, o (( S. = f== + [Ba, Bo,l concave), (19) Cvl AE(ri
where we recall w!! A (0, (()). The interval [Ba,, Ba, is such that [B,, B - hr, (LBs, B...). Note that [B,r Bo.] is known because B., and Be, are known by Assumption 3.1 (reell that, by point (2) in Proposition D.4, the bounds B B., BBs are inherited from y/s to vh.e)). We want to highlight that for any fixed E SN-1, the problem (19) is not infinite dimensional, indeed we only need
to recover n variables (d,(w() (t)) ós(w, (t) )..., :..::::ww (s(w! E Bol. A full discussion on the optimization problem (19) can be found in Appendix H.
Remark D.5. The problem in (19) serves purely as theoretical intermediate step for establishing the regret upper bound in Theorem 5.4. In practice, we do not compute $1. for every 0. As discussed in Algorithum 1, we only solve (19) once, with 0 0. to obtain &i Lerr Moreover, by point (4) in Proposition D.4, the function Vi.o is increasing (for sufficiently close to 0,). Since ha, is also increasing, it follows that 0h inherits this monotonicity. Nonetheless, we did not include
17

---

Published as a conference paper at ICLR 2026
this monotonicity constraint in the definition of S in (19). This omission is justified because the theoretical convergence rate in Theorem D.6, and consequently the regret upper bound in Theorem 5.4, is driven entirely by the concavity constraint, which imposes a higher-order smoothness condition than monotonicity. However, we do enforce monotonicity in the algorithmic implementation in Algorithm I.
We are now prepared to demonstrate the convergence of the to 1. where
L ha 0i.0-
Theorem D.6. Let Assumptions 3.1, 3.4 and 5.1 hold. Then, by Proposition 3.5 and Proposition D.4, Vie is 8y-concave, where 8, C, > 11 Let m mn, where Su Ju(u) (u)du the proportion of data points {w Jee(n) lying in the U + oc. For every Y there exists my, a constant E; > 0 and C, 0 depending only on constants in the assumptions such that
P
sup OEEN
sup melf..
(u) 2 e()) S 6. ((((((mmmmm33// 2 1 1/m--2, 2 mo.
(20)
where Um {u El U [u dm] C UU, with dm (1oo(mmmmmm/ More specifically,
L
4v7BB, 70; v
B² + +B² 4:
C, = max
Bogs"
(21)
3
B², (Co) (8)
where L = SuPeESN-1 EEU ((.(())((oo())
is such that infoesx-1 inf for fut > Cg, and o, is the sub-gaussian variance proxy of the error Es.
Cg
Moreover, for 0 02 we have
E
sup 1, (u) (c(ww]] 0((1oa(m//mm221) 22/5.
(22)
LuEltm
Proof of Theorem D.6. We first prove the concentration inequality in (20).
Let m an be the asymptotic fraction of points lying in U, where n is the sample size and Su f (w) dw. Define the empirical fraction of points in 2 the random quantity
a
in =
1 1w eu).
By Lemma H.9, the event
π
2
En
holds with probability at least 1 1/2(n 2)7 for some 7 0, provided that is sufficiently large and 6, + 0 as n2 + co. Now, we apply Theorem H.5, using Remark H.6, with the following substitutions:
4o - v
E 5 V... a + 2, s h ha d
where hs, is defined in (4). Intersecting I with the high-probability event in Theorem H.5 yields the desired result. The only remaining step is to verify that the assumptions of Theorem D.6 imply those of Theorem H.5.
(1) thee is s:-concave for some 8; -1. According Proposition D.4, this condition is satisfied provided eh is concave for some s; > -1, which holds by Proposition 3.5 and Assumption 3.4, with C:
18

---

Published as a conference paper at ICLR 2026
(2) Assumption H.2 holds uniformly in 0 -y-1 because the design points are drawn from an i..d. elliptically symmetric distribution with density generator g > 0 and then fp > on any bounded interval. Thus, inføesx-; infueut feTp(u) (u) Cg for some Cg 0.
(3) Assumption H.3 holds because yi are sub-gaussian (indeed t); is bounded and e.") are sub- gaussian) and v/,oa bounded uniformly in A E Sx-1 by Proposition D.4.
(4) We prove that Assumption H.4 holds uniformly in 0. Recall that 0i de, o vi.0 (where ds, & ha. is defined in (4)). Then v/(,(uu) = d', (v),(()))((())) For every u, E u and
0 E -x-1 we have
(w) (()(v) = Id', (Vra(())) (1,
I |d" (vro()) (V. (w)) + (v)
The first component Id", (u)) La = sup,, d", (x) depends only on 8; and bound of th. The component ( is bounded uniformly by Proposition D.4 point (4). The other component ( ((o - T./u o
(vi I La ol by Appendix H.I, where
for some L > 0 independent of by Proposition D.4 point (4) and (d", (vie (v))) is uniformly bounded by Appendix H.I. This proves that vho Lipschitz uniformly in 1 E SN-1-
To prove (22) we apply the triangular inequality
w ., (u) (x)) 16 L. (u) V.. (u) W:, (u) (
and for the first component we apply the concentration inequality in (20) while for the second we use point (3) of Proposition D.4
(w) (x) x ||0, 0:112
and then the concentration inequality Proposition D.3, while retaining the dominating term (())))
19

---

Published as a conference paper at ICLR 2026
E
PROOF OF PROPOSITION D.3
For simplicity, we redefine 7,") as {1, (1.
nnnnn.. x(1)
= -p(0)- -p. The loss function 2{(0) is defined
2((0) 1/ 0 x(!
Then the gradient and Hessian of (0) is given by
Vz 1 n
Σ
0 1xxli x(1) - v! x(())
t=1
1 Σ 2x x01
(g22(0) = VgL2
Let 0 be the global minimizer of [()).. We do a Taylor expansion of (.(O,) around 2,O,, with X;
to be determined:
2. - (1.0.) (100)= - -100) - 2 -
1 (0,
0,0, V (0. - x.0.))
As 0 is the global minimizer of loss L.(0), we have L.(0,) s L, (A,0,), that is
1 (0. 00, X,0,, V22; (0. -110)) s 0.
V I. (1.0,) 2, +
which implies
n1
0. 1, Σ
x (1) (0) (0)x0(((0)) (0,- -2,0,)
,,,0 - -.) $ Vo ,,,0,
n1 1=1
$ Vo (2,0 11 11,0: 0
$ v N Vo (,0,))1 1 0.11
By Lemma 1. the LHS satisfies
0. - X,,,,
10 (T) (0, - x,0,) (1,0),
Smin
|x,0 - -0,112
2
w.p. least -e- oomi.. n/16 (for n sufficiently large) for certain constants that depends only on the variance proxy 0₂ of the sub-Gaussian random variable x(9) and by Lemma E.2 the RHS satisfies
N log n VN VI (A,0.) 14,0, 0.112 S A
|A,0, 0.112.
n
with probability least 2N (as long as n N), where D is a constant defined in (23) that depends solely X; and the variance proxies of the sub-Gaussian random variables y, (t) and x Putting the two inequalities together we get with probability at least 1 2e esiin n/16 2N that, for sufficiently large
N logn
|A:0; - S B
where B.-
Ld. Now we conclude. Recall that A, where X, defined in (25). Let
Wn {0: 00: 1A,0, 00:1100000
N log
0112 < Bi
20

---

Published as a conference paper at ICLR 2026
Let n. be large enough so that 0
N log
S d₂: this guarantees that any 0 E W,, is such that
| 2a Lf which come from the fact that ||
2 A. Then for 02 Wa we can write
0:
0
||0
0,112
0,
1
1|
A
||0
0
1
1
+
0
A
A
10
11
0x
0
1
1
+ 10 1l2
X
A
1
1
11..0:
0.112
A
1
+ 100112
0
Ax
|A.00 0.112
11
2
|011|
+
A
X
1
0.112
$ 2
A
and, as 0, E W,, with probability at least that with the same probability bound
comm n/16
2N for n sufficiently large, this implies
N logn
- - S Biy
n
where
4/2 Jz (Nr0 + oy,)
B. 2 A
A:Smin
AiSmin
This concludes the proof.
Lemma E.1. There exist > 0 such that with probability at least 1 2e - we have (Smin/2) & En for n sufficiently large, where
En
(0).
11
Proof of Lemma E. To get lower bound of the minimum eigenvalue of Σ,, we use the following remark 5.40 of Vershynin (2010): let A be x N matrix whose rows A, are independent sub- gaussian random vectors N with second moment matrix E (non necessarily isotropic), then there exist C > 0 depending only the sub-gaussian norm az. such that for every r 0 we have 1 E. A,A Σ|| & max(6, 82} with probability at least 1 2e -or where 8 C N
v
In case, since Σ,, is average of i.i.d. random matrices with mean Σ E (() and that {x()) are ub-Gaussiian random vectors (recall that x(9) sub- sub-gaussian because the generator satisfies g(x + y) ( for all xr y), then there exist c, C such that for each r > 0 with probability at least 1 2e- -or
N
Σ,
Σ < max (6, 62,
} where 8 & CV
Here c, C are both constants that are only related to o₂ sub-Gaussian norm of (1) Now, choosing
Smin 77/4, 4, then long as NN6C2 /S2nn we have 8 CV4 + Smin
Smin
Sman
Sant
2
Thus with probability at least 1 2 n/16
n/16 we have
Σn Σ1 S max {5,02 & max
Smin 2
Smin
2
4
21

---

Published as a conference paper at ICLR 2026
and since Sminll & Σ & Smaxx we get Sminl - In $ Σ- En S Smaxt - En max { {Smin/ 2, sminn/ 14).
and considering the first and last term we get
Smin
Smin
}) 1 x En:
Smin + max Smin
2 4
and since Smin + max
Smin
Smin/ we get (Smin/ /2) II o En.
Lemma E.2. With probability least for sufficientll large, we have
Vo. (0:) 11100 S "8." Vloooo)g/n
where
= (Maaz + Ty.)
(23)
is a constant that depends solety on X, (defined in (24)) and the variance proxies yy and og of the Gab-GGassian random variables / and x(", respectively.
Proof of Lemma E.2. We first prove that for all 1,2, ...
E [A.0] (())
-
(t) )x(1)
Using the known property of elliptically symmetric random variables (see, e-g. Li (1991, page 319, comment following Condition 3.1) or Balabdaoui et al. (2019, Section 9.1)) we have that
E (4) 0. (1) = 0.7 (bb,
where b is vector that has satisfy E [x xx(x)]
var(O, x(1)x or equivalently (using
var(x(()) Σ.), b (0, 500,)-1 We have
0, x(()) y) [0] = X var 00, x+)) }b E y x1)
E
X var(O, x0)) yb E
E
0 x
= A var(O, x())) 36 E
(. DE x(1) 1 x((1)
A var(O, x(())) E Ws x x0 x0
(>, var(0. (() cov
W) x! )) 0, x(())
which is equal to 0 as long as we choose
A cov ((),(()))0)) x(1)
(24)
var(f) x(())
Note that A; > 0: indeed, as th is increasing, it implies that, given (()) independent copy of x(()
0 E 1/ (0. 20) th 0 (oTx(())
0. (0 - 0. x[T((')] ]
2 cov (vs (0)x(() 0, x())
(25)
Thus, E V. (A,0:) = 0, then every entry of V (A:0.) is mean zero, i.e.
E (A,07 (1) vi (t)
(2) 0, i= L, I.
(1) Now, since U; is sub-gaussian (because E (1)
is sub-gaussian) with variance proxy denoted as dy. and (() is sub-gaussian (because the generator g satisfies g( y) g(x)g(v) for all wr y) with variance proxy denoted as Ja. A;O,T (+)
is sub-gaussian, and given that (t) is sub-gaussian, (t) is sub-exponential. More specifically
the product (A,0) (t) vi x
11A,,0xxx y (x((")) 1l,, = 11 (() (2) Il ||,g{"00 11
< (A. x0 + l1u I ) ||x(())) llez
I (Naz + oo.)o $ vi,
(26)
22

---

Published as a conference paper at ICLR 2026
1, with 1. For p 1, || oo is equivalent to X belonging to the class of sub-exponential distributions, while with p = 2. || 1bt < is equivalent to X belonging to the class of sub-gaussian distributions. Then (A:0, x(0 Vi
where || lle, is the Orlicz norm associated to (i((2) c² 1,
(1) x ~ SE(U,, vs) for = 1,..., N, that is
IP (A.0 x0) - (1) (t)
u) S 2xpp
min min
Now, using that X, 2(2,0, x(1) -- ) 1 SE(r? vz) are independent for all t, with B(X;) we get
P (/
2u)= =
2(1 x(1)
-x 1
NP
2(1,0 (1) -/ )10)) (0)
2 u
t=1
n² vs 1/
$ 2N exp
min
By taking u = V2v, log.//og////// n/n, for sufficiently large n we have that
u²
u²
min
1/
and then
logn
log n
V (0.)l S V/201
with probability at least - 2.e -lg((n) = 1 - 2
23

---

Published as a conference paper at ICLR 2026
F
PROOF OF PROPOSITION D.4
F.1 PROOF OF (1)
We have p EN A. be an elliptically symmetric random vector with density
(p(p) = (p - m) Ap- -p- mm),
where m is the location vector, A is a positive-definite scatter matrix, 9 is the density generator, and k is normalizing constant. We wish to find the conditional density of p given 0 p u, where E RN is fixed vector. The constraint defines a hyperplane:
H. (DERR -uuj.
The conditional density satisfies:
S P x fp(p), pe Hu,
that is,
SpjoTp=u(00 (p)
Z(u) 9((p m) A Ap (mm))) for p such that 0 O'p u,
where Z(u) the normalizing constant. Define the transformation:
y = A (p -m),
where A satisfies A = AAT, Then, since (p (-m) T (p - m) = y y, the density becomes:
fy() gly" y).
The constraint transforms as:
p-p=00 T (m + Ay) = T m + (A y)
Define v = A 0, so that the constraint simplifies to:
y
m.
(27)
Decomposing y into components parallel and perpendicular to v. we write:
| + a, with v T a = O.
(28)
Then y y yी ||a21/2 From the constraint in Equation (27):
(11))
0 m ||1||2
u m Since the original density in the y-space is
||1||2 y1 a
u -T
2
fy) x g + [la)))),
when conditioning on V1. the conditional density on the (N 1)-dimensional space of a is:
faw (a) x g ( 11122
0
+ ||a0 l2
Now, using the assumption that g(x + y) = g(x)g(g) we have that
ToloTyu-o-mle x {(((a{))).
(29)
Now, recall that
v u
m
p = m Ay = m +
|0
|21122
a
= =m,- + Aa,
(30)
24

---

Published as a conference paper at ICLR 2026
where we defined the conditional center (the "shift")
0 m
(u
0 m)
my
A
AO
(31)
10 |
A0
Thus,
V1. ()) (c. (H) w, = u)
(Bc, (1/i p) wi u)
(v) p) w, = u)
EP (w: (0. p) p 0'00 u)
(30) Ea (e's (0, m. + + Aa)
v y = a 0 m)
(29) di (0. m. + 0. Aa)
g(lla 133)
JgN-1 g( 12) do
(32)
JN
This completes the proof of (1).
F.2
PROOF OF (2)
We first define
d
T.T A0
c(0) 0, m
(33)
du
0 ATA0
A00"
= m + AO (w-ot (T)
where we recall from Equation (31) that m,
Note that
0 0TA0
Ic(0)| <
Cmin
05 S
Cmin
10:12|100 S
Cmin
(34)
Cmax jEN
Cmax
Cmax
where we used that 0g 0 SN. By (32) we have
vi,0(u) /
u E U, 0 E Sy-1- JAN- 1b (0, m. + 0, Aa) g(a)da,
al |[||a where ğ(a:) = JaN-1 (6
is independent of u. Then, for k = 0, 1, 2 we can write
6 (u) c(0)* / JNN-1 10 (0, m. +0, Aa) g(a)daa
(35)
proving that Vi E (2() for all O. By Assumption 3.1 we have that 0 < Bs, S t/ S B which immediately implies that 0 < B S vi.0 Bv, uniformly in 0, proving point (2).
F.3
PROOF OF (3)
We can write
(v) vvx(w)) = f 1ạ/s (0, m, + O, Aa) (((u))](a)da
< N-
10, m. + 0 Aa ulğ(ax)da.
25

---

Published as a conference paper at ICLR 2026
Note that
(u θ m)
10, m. +
Aaa Aa
ul
0, m + A0
+ 0, Aa
0 AO
(u
0 m)
0- Acx=0 by Equation (28)
0
m
+ AO
+ (0; - 0)
Aa W
0 A0
0
A0
0,
S 100 0 2| Ao
2 +
m 1|
0
0
+ |M
A0
ATA0
0 A0
0 A0
8 110 0122|10012 +
0,
0
1
0 A0
0 A0
2
0, A0
0 A0
$ 110 0122|10122 +
0 A0
A0
(0 T Ao
100 012/|||112 +
0A0
A0
2 110 0122|10112 + 110, 0|12
0 A0
A0
S 110 0 0|2||00122 + 110, 0|l2
0 A0
Cuax
||0||
$ 10: 0
0|2||0112 + |00 Cuin
|0
0. 0 2
| 12).
for some c > 0, where the second inequality we used that E Ur which is bounded set, and we also used, at different points, that |0:112 ||0|| 1. We then have
(u) - v)((u)) <
10. m. + 0 Aa - ulğ(a))do
RR--
< 10, - 011
-0022 c+
RN-1 lall2((a)da)) 2 |10, - -1122.
where we have used that
f J |all2ā(aa)da
JR 9 (( JNN-1
finite because since g( + v) = ((z)g(v) then g has exponential decay.
F.4 PROOF OF (4)
From (35) we have
ko = c(0) { vi (0. m, + 10,Ao. g(ar)da
gN--
where c(0) 2 d 0, m., R No as defined in (33). Then we only need to prove that 0, A0 0 for du
A0
sufficiently close to 0,. Recall by Assumption 5.1 that N is symmetric positive definite matrix with Cuin T & A & Cmax II for some 0 < Cmin I Cmax < oc, and that ||0||2 = |0,1] 1. We are interested in the conditions under which
AO, > O.
We begin by writing:
T ATA;
0.- A0; + (0 0.) TAO.
Let = 0.T AO,. Since A is positive definite and |0:|| 1, we have
a 2 Cmin >> 0.
26

---

Published as a conference paper at ICLR 2026
Next, we bound the second term using the Sauchh--Shwaand inequality:
1(e 0.) T.ol -
0:112 ||A0:|l2-
Moreover,
||A0; S Cmax 100:11 Cinxx
Therefore,
A0 2 a Cmax 11 04112.
To ensure that A', > O, it suffices to require:
0 0s112 <
a
Cunxx
We now prove that [o & Ic(0) BB,
Smin Bas Lastly, we prove that vh is Lipschitz uniformly
E -y-1. For all u, v E U, and SN-1 we have
(V),(()) (())
[ RN--
ui (0. m + 0,T Aa) g(a)da JaN-. vi (0, m. - Aa) g(
= =|((0)
Assumption 3.1
0 m, - 0.'m. m
Gmin 0 (m. m
Bull Cmax
Cmin
Bug
m m
Cmax
(u m
m AO (v- T m)
Bel Gmax
Cuin
m AO
ATAO
0 A0
Caiin
||A@||
min
By
S
Buy
[u v/.
Cmax
0 A0
max
F.5 PROOF OF (5)
Recall that
[ JgN-
wi (0, m. + Aa) g(a))a - th (E(a,, u)) ((a)dda
viro(u)
where
E(a, u) = 0, m. + O,T,Aaa Ac.
First note that if 0 O,, we have E(O, u) since 0 Aa 0. and then vi.00 1) Now suppose 0: * O. More generally, we will prove that for non-negative functions h, f1, f2 integrable in that satisfy
1((1 A)x + Xu) 2 (a() A, 2,y E R
then
H ((1 A)u1 + )wz) 2 M, (Fi (1)) U1 u2 R.
where
1(w)) & / ((((a,))ddPaa
F2(u) & / IilE(a, j= j=1,2
where P is a probability measure.
27

---

Published as a conference paper at ICLR 2026
Lemma F.1. Let 0 < on satisfying
oc, and f.9. and let h nonnegative be integrable functions
(1(1 X)x + Xy) 2 M.([I(=), A, 3, E R
For every fixed u E R define H, F1 and F-2 as
H(u) A / ME(a,
(J(M)= & f IslElo,u))aP(a) j j 1,1,2
where E(ox, u. = ax T + cu + for non zero vector b, nonzero real value and a constant and a probability measure, then
H ((1 A)ui + Xu2) Me/(o+1) (Fi (ui). F2 (w2); 1 X,
u1, U2 R,
where have defined
(Ax*+m19)) 3 8 0
M. (x
8 0.
Proof. We have
H((1 A)81 + Auz) / MEE(o, (1- A)mn + XP2))
We write
E(or, (1 - AJui + Auz) = a a + c((1 A)mn + Au2)
= a)(eu + a bb] A(euz + a bb]
= (1 - x){((r, u1) + Xg(or,
and by assumption on we have that
h(E(a, (1 A)u1 Au2)) 2 (1)) u2)); A, A).
and then
H((1 - A)41 )uz) 2
-
= M, (M. (((((la
/ u2)((a 2.2)
M, (F1) Fa(u2): A,
where in (+) we used that for -1 the map
(x. + M, y: 1 X, A) = [[1 -)x=* + X/
convex on (0, oo) x (0, oo). and then we can apply Niculescu Persson (2006, Theorem 3.5.3), which is extension of the Jensen's inequality for in 2 variables.
0
28

---

Published as a conference paper at ICLR 2026
G PROOF OF THEOREM 5.4
We compute the regret upper bound of single firm i. Recall the definitions
rev;(p) p-;) pvs(-Bipp + Y p-t), rev,(p p-i) pVio (- %/ p-i),
so that
Reg, (T) E rev,
( (T. _².))= (e, |p_)]}
where
(p argmax PIEP, (ev By optimality condition of T, have
pj argmax pEP, revi(pi p= -
rev;(1e)) (9)
1T rev. (
Op (w) (p (v! (p))
20
0,z rev p P_))pppp pa- (p. (0) -r))
(t)
for some p' in the segment between the points p; and (p From this, we derive
(1))
(2) S - 0g revi(p | (T.(p" -p( (Tx _T) rev:(z))
Now, note that
-G revi
(1) p 1== 28,01(1-1 + ( - 3& (-B,'' + +TTp0
23,,Bbb +B.pD. Bul
where we used Assumption 3.2: 0 < B S 3/ s B and |u!!1 S Buy on l for some (unknown) Bay, Bu Buy > 0. This implies
(ev P ( (e, (1)
(0
$ (T.(P (1) P 12
S |T(p(() (1) p 10
$ (T)p())) p'11 + l|p 10
= [[ - -r(p") + +|Ip" - (013
S llp()) -p"ll + +|pp" 11pp-p"01
x (t) p*11
(36)
Observe that this implies
T
Reg, (T) S E p - 1111
(37)
Lemma G.1. If Assumptions the Theorem hold, for T sufficiently large we have ElsuPpEP (1, p) N. (0. p)ll S NivN(1o022211 where X; = max (C,, and D, and E; are defined in (17) and (21), respectively. Moreover there exists unique value Kę E 10,
that minimizes Elsup lv. 0 p) Vi. (0) p)]]. This value satisfies the implicit equation:
1/10 K 5 - -x,)7/5.
Lemma G.2. If Assumptions in the Theorem hold, for T sufficiently large, supper (v p) L (0, p)] 6 implies (!) p'1 & N SuPiEN + T 2(1-r11) for every t +1
29

---

Published as a conference paper at ICLR 2026
By Lemma G.1, Lemma G.2 have that for t + 1 with 7 sufficiently large,
(36)
[[rev:(T.. |T_)) (ev (9)
x E p 1'1
Lemma G.mmaamaa G.2
[log
2/5
2,N3/2
2(1---1)
(38)
and a consequence, give that 75, for every 12 7 +1
Reg, (T)
rev, (Ta(p (T rev: |o_)
T
+ E
(T; (0) _ (ev; |2_
(=
S (T - 7)
log
2/5
L
2(1-T-1)
t=
log
2/5
T-T-1
S T2,88/88/2
+
L
1=
log T
2/3
T 2(T -T)
T + T2;N3/2
T
L
< T 2, 26/5 3//2
(log T)
2)2/5
+
Note that we are retaining the dependence on 2; = (si) to demonstrate the way that 8; affects the rate of the regret. Substituting back the value 7 T into Equation (38), we get
[l (0)
p'1
S 2,N
9/6
I 2t 2(t-r-1)
log 7 S N,N //
2/5
+ LT
211-7
Tt
2,N 8/2 25/0 (log T7 3/5 + LT
2it-T5-11
and for / t T
E (T) p'1l & 2,N% 28/0 (log T) + 1 2(T 2(T-75-1)
This completes the proof.
Remark G.3 (Dependence of the regret and NE convergence rate on 8;). The value of & that minimizes the expected regret Reg, (T) is obtained by equalizing the exponents of T in the upper bound T +T1- ignoring logarithmicc factors. Solving this balance gives 5/7. Consequently, for each E N we obtain
Reg, (T) 0 H, N / (log 3))
-p'1 o 2, N // T) T.p (
T co.
These bounds retain the constants Y, and Lr because they depend on the parameters $1...., (or equivalently C......CN/ C.). Note that the dependence on {sy [Sy]eeN) enters only through the multiplica- live constant 2; and the additive constant Lr, never through the powers Tf This makes explicit how the choice of s; influences the regret and the convergence the NE. Below we show that if 8; the optimal-concave parameters (as defined in Definition L.3), i.e.
8; =uup 12 sup (v)x(u) vi (w) (1, ()(((()))]] s s0).
well.
30

---

Published as a conference paper at ICLR 2026
then any misspecification 5/ 8; satisfying
1
1/4/+1| Ihll
sup
ieN
A
does not affect the regret or the NE convergence rates.
(1) Multiplicative constants L, The constant H; = ,,, D. contains B, and Eú (defined in (17)-(21)), which are the mulriplicative constants in the concentration bounds for
1| - -0,,0,1,1 and
10, 08
respectively. Any value & does not affect the rate of linear estimator 0,, but it could introduce a bias in the estimator L.;;; Precisely, if we choose 84 S 8ú, the inclusion property of Proposition L.1 implies that an si-oppimalcooccaeee funncie remains si-concave. Thus no bias is introduced in the concentration of || , Ilso, whereas choice $ >> would. Then for s S Si, since Bg and Ci are uniformly bounded in Sú, i.e. Bi, Gi < C for some C independent of 8i, they do not affect the regret NE rates.
(2) Additive constant Lr. The constant Lr is the contraction modulus of the best-response map and determines the geometric decay term in the NE convergence. Convergence holds whenever Lr E (0, 1), or equivalently supieM [|si]l m/l1/3; < 1. Because g((u) = - 1/x((17 (u)), we have
1- (() 1I,
G ==
6
Thus any oy satisfying supteM 11-1//11 11/0 < preserves contraction. If 2 1, contruc- tion fails and the regret guarantees break down.
Combining both components, we conclude that as long as the sellers choose s S 8; (where s; are the optimal-concave parameters of thx) and suPieN 1-1/4/11 Itall < 1, the convergence rates of both the regret and the NE remain unchanged.
G. PROOF OF LEMMA G.1
Let 7 be the minimum exploration phase among the N firms and t E 2, Let n be the length of the exploration phase estimate 0: and (2) the remaining length for estimating the
N log (1) n
link function d). Define the event ε {1|ē, 0,1l s R R,, where R R_ Bi
where
B, is defined in Proposition D.3, and
(p. 2 (- + 7/ p- - V. (-3p.. + 7. p-))) Pt E P.PPIEE P-
We write
(p:lp- (p: (p:
Analyzing the
By Proposition D.3 we have E| (pr --))( $ P(E)) = Q,!0) = 2e 2e-essa 2i /16 16 + (05
Analyzing the B (p.Ip-))IEE))
1 (-3.p: + 7TP-s) 1/,00 (-Bip: .,. p (T&)
=1
+ Wa, (-Pip; + +% p-i) Vi.0 (-Bip: + 7o ((E)))
+ We, (-Bip; + + p-;) - vb:( 1Bppp + 73 ((E,)
31

---

Published as a conference paper at ICLR 2026
Analyzing A & Define the event O {supoeu 10,00 (u) sufficiently large, by Theorem D.6 have that for every 7 4
v1 (u)l
Eip ( For n
1
P(O.) 21
(m (n
Consequently,
B(A) [[AI( Q, (&)) (EII((AAI)))) (
S E
sup
16 1.0.
(w)
4 o. (u) (w) nE) + P(,
well
2/5
log n
= 6;
P(O: N&) + (P)
(2)
ni
SI
log ;
(2)
2/5
S C;
+
n
(2)
(m
(2)
y
2/5
log n
Ci
(2)
where we chose y and n (2) sufficiently large.
Analyzing B on & By Proposition D.4, 1/,,0, is Lipschitz, then
(N nig
1/2
B[BI(E)) & |0: 0.112 s R0,00 Bi
n; (1)
Analyzing C on E; By Proposition D.4 we have
log n (1)
1/2
1 (u) (())EEI((E)) z 10, 0:112 - n(
B,
n2 (1)
Combining the terms
(p and (p ((EE): We got that
(2)
2/5
(1) log n
log n
{p:ppp
8;
n2
Bound of the parametric associated with
Bound of the parametric associated with
We now derive the optimal choice of Kę. Since (p:lpp- appears multiplicative factor in the
total regret we want to make (p p-;) as small as possible. Using that (1) = TK4, nz. r(1-k.). excluding log-factors, have that
A.p.pp- -2/5 + (,N.1 11/2
2/5
We want to minimize the function
[(n;) = (((T(1 kx)) - 2/3 + D. 222222(TT5))
for constants > 0, N > 0, and K4 E (0,1). Define for simplicity A; -2/5 B,
2/2 1/2, Then:
1/2 ((a)) = 24,
B 3322
f(e,) = A,(1 - k;) 2/5 + B
(1 kg))
-7/5
2 Ri
5
32

---

Published as a conference paper at ICLR 2026
Setting (Ka) 0 gives:
2A,
(1 - ks.-
3/2
5 B,; 1/10 k,)
2 K;
+
T
5
4 A;
Substituting back the expressions for A, and B::
3/2
1 11 k;)
C
The optimal K² E (0, 1) satísfies the implicit equation:
3/2
N1/22 11/10 k;)
We now prove that there exists a unique x satisfying this equation. Let g(K:)
K;
a8 8; N1/22-1/110 8 / - k,)7/5 and note that g(0) = -
0, g(1) = and
g g((x,) = 1 1/2 + | 2 1/10 n2, > Note that, since we are excluding all the
constants when upper bounding (p.lpp..). the optimal value n. is independent of i and only depends on the exploration length and number of sellers in the market N.
Now, since the optimal ky E (0, 1) is fixed, and m! term is
1-s (2)
Kf
n2
(2) x n
we have that the dominating
Re(pe(p-o) Ei 1ogg(T(1 - ki)) r(1 - kis)
2/5
log(THe)
)
1/2
log logn n
(2)
2/5
Bi
N
S L LVV
TKi
n1
(2)
where 2i max (66,, B.).
G.2 PROOF OF LEMMA G.2
Recall the definition
(e p-i) p p-1), revi(p I-i) =p po, (-Bip 7/ p-i),
and
(p(p.) = argmax rev; p--), P.(p-.) = argmax pPP, rev:(p: p_.).
We have
sup pEp
(pv: p-i) - revi(pi 1--)) S p sup
(A. (. S 4.
pep
Then we have that for every p E P.
rev, (Tv,(()pp p fov, |p- p rev,(f,(p_.)) p 2 rev, (f. ---))-6--
that implies
rev; (T)((p(p))ppppp--eee (p-) p-.) S (T. p rov, (
+22 S 20,
Now define
#: := 23:B B.D.Byt
which is strictly positive by Assumption 3.2. Then we have
26 2 (ev,(TT(pp..) p-,) rov:: 1p;))
14 (T((p-)) - -f:(p.))3
This implies
[T(p) - f(p)l2 = Σ -filp-))f((p__-.1 <
C2 Σ iEN
<
N
sup iEN p4
E =;e, V.E..
VeN
Mi
33

---

Published as a conference paper at ICLR 2026
This implies that
[[[(p) - ((p)lla c.
sup PEP
For every t 2 T + we have
(p
p'112 (T p'll2
- |T - r(p (1-1)) ||2 + [T(p(--1) - r(p"))
S E Lr|pp (t-1) - p" 1l2
cc Lr(ct + Lr 1p ('-)) - -p"ll2)
=e(1 Lr)
+ +L 11 -p"ll
8-1
Σ T
+ 11 (1-0) - p2112,
(1,......
S c 11-L
+ 1
(1---11 |p ((-(t---1) 1i) - 2
= 1- + I (1----1) || (T+1) p'112
S 6 f-
1 + mmax (1-
(39)
T
We conclude that, for every 2 T + 1,
( p'112 2
1
2 +
L7 2(t-r-1)
1-Tr
= 8
T-
N
sup
+ 88pppss LT 2(1-r-1)
iEN pi
< N sup
+ T
2(1-T-1)
iEN
where we have absorbed the constants 8
and Sp Tmax
1-4r
minze p4
34

---

0 Published as a conference paper at ICLR 2026
H NPLS FOR S-CONCAVE REGRESSION
Inspired by the work of Dümbgen et al. (2004), prove uniform convergence result for the NPLSE of a mean function that can be written as an increasing function h composed with a concave function Φn- Suppose that observe (U,, Y1), (U2, Y2). :-.-; (Un, Yx) with fixed numbers U1 s U2 s S Un and independent random variables Y1, 22, Yn with
E (Y U U = u) = t/o (u),
for unknown function vo : u + (0, o0). where U is an known interval containing
g {U, U2...., Un
Assume that
vho - h o Φo.
(40)
for some known increasing twice differentiable function h : R - (0, and unknown concave function do l + I.. We denote the class of functions 4ho that can be written as h do with Fu. which includes log-concave functions (h(x) E*) and more generally s-concave functions for every real (h(x)= (-z)1/s if < 0 and h(z) 1// if > 0).
Now we go back to the general known transformation h. We assume that eio E [B B&] for some known 0 < B. < By OC, so that 4 = {u By S vo(u) < B. Let [Bz, Bbl C IR such that [B..: By] = h([Bs: Bøl)- Then h' E BB, Bp] [Bg Ba) for some < Bn < B₁ xo, where B₁ and B₁, depend on B. and B5 Note that B, B, are well defined, indeed, by Weierstrass theorem, /' is locally bounded, that is for every compact set K there exists O < BA < BA < +00 such that B₁ S N S B₁ in K. Then we write
Fn arg min DEC
(()) - 1 hod (o))))
(41)
Sn e h ho 2n.
where C is the set of all concave functions :u + [Bay Bo). Note that the problem is not infinite dimensional, indeed we only need recover variables (œ(U1), ((U))),(UU))...... (U,)) E [Bgr Ba]. When h(x)) x (or equivalently for 1-concave functions, i.e. concave functions), (41) was studied by Dümbgen et al. (2004), for which on exists and is unique and doesn't 't need restrictions on the codomain of Φo. that is [Lg, Bb] can be the whole E. Existence and uniqueness come from the coercivity of the loss L. which not necessarily the identity map, we rely on Weierstrass' theorem (which guarantees the existence of at least a minimum for continuous function F $2 C R - ER defined on compact set Q of R"). Thus a solution of (41) exists (but might not be unique) because the n--dimensional variable (o(U1); (UU)...... (U(U)).)U)))
property that only applies for l(x)) x. Since in our case is
(U,)) E [Bg B&] where [Bg- B&]] is compact. Uniqueness not an issue in our case since we only care about the construction of a consistent estimator. Proposition H. which is followed by Lemma H.7, shows the constraints on the codomain of Φo when vho :u + [B B
is s-concave for * 1.
Proposition H.1 (Constraints for s-concave transformations). Suppose that vo is s-concave, that is 4/o h1 o Vo for some s + 1, where h2 = =d as defined in (4). Then
[log B,), log( BB)]
Φ E BB Bøl 2 d, d. B
B
B
8 <<> 0
:
B Bil.
8 8>0 0.
We now establish the assumptions to guarantee the convergence of the estimator defined in Equa- tion (41). We consider triangular scheme of observations U, Un.: and Y, = Y,.; but suppress the additional subscript n for notational simplicity. Let Mn, be the empirical distribution of the design points Ug, i.e.
Mn(B) &
EU, BCR.
1=1
35

---

Published as a conference paper at ICLR 2026
We analyze the asymptotic behavior of th, fixed compact interval
[a, b] C U,
under certain conditions on M. the probability measure of the design points, and the errors
E Y vo (U4),
i 1,
Assumption H.2. The probability measure M of the design points satisfies Ml ((u, 2 Cu for some Cld > O and for all u < v with u, U E U. Assumption H.3. For some constant max Eexp (nFa)) S exp (o2)22/2) for all μ R.
Assumption H.4. There exists a a E [1.2] and > such that for all u, E [|
{ (uu(u) oo(v)] L/u vl (0)()) (v)) I L/u o wja-1 ifa>
ifa=
(42)
Assumption H.2 holds the density fu of the measure M is bounded away from zero, that is fo C.e. which is standard assumption for uniform convergence of non-parametric functions (see e.g. Dümbgen et al. (2004); Mösching & Dümbgen (2020)) as well as for I convergence (see e.g. Groeneboom & Hendrickx (2018); Balabdaoui al. (2019)).
Theorem H.5. Suppose that Assumption H.2, Assumption H.3 and Assumption H.4 are satisfied. Let Φn be solution of (41), and let &n. = h o Φ.. Then, for all y > 4 there exists integer ny and a real value > O such that
(logn'
4/2u11
IP sup b,
(vo(u) Sn(l)) 8
2 - 10222=
no:
n
where '6 depends on C.u. Bi, BBd L, a, and 7 and 8n (log(n)) /20-1 for some l
(L, a). More specifically, &6 needs to satisfy
4 L BR
4V7BBT0
B₁ B (C
E M max
B
The proof can be found in Appendix H.3.
Remark H.6. If tho and Vn depends also on parameter O E O $o,0 and Vn o. for which the domain l does not depend on O and such that Assumption H.2 and Assumplion H.4 hold uniformly in O O and all the constants C.u. Br Bay L, a. Y, a, b are independent of then
a/20+3
log n
sup sup (w) (n)( 86 uE uEla+tn, OEe
2 1-2n 2n2-
H.1 TECHNICAL LEMMA
Lemma H.7. Recall the definition
log(y),
s = 0,
dv(y)
-y²,
8 << 0, 0
y"
0, 0.
Then holds
0 OcC, 5,,))dd,Cl (B.))) and (B,) < d" < C²,( uniformly on [B,r Bol,
where
d"(B,), 1<s<2
(,,),,,, 8> 1,
{0). s=1
(B,)
1.
and C.
(43)
(2). 8 =
d,())),
8 1<1
(B,),,),, s s (1,2),
36

---

Published as a conference paper at ICLR 2026
C. < for < and C² > for 1. As a consequence. for every real the function h2 d
increasing on [B By] with the following bounds
S h -
(pp)
Proof.
s s= ==0,y>0
{ -
8 s= ==0,y 0
d'((v)
d'(r)
|sly""
s 0
|s|(s 1)y²
s 0 0.
Case 1. 1. Then d' increasing and d" is increasing for 2, d" 2 for and d" is decreasing for E (1, 2).
Case 2. 8 = 1. Then d" = 1 and d" = 0. Case 3. s < 1. Then d', is decreasing and d" increasing.
Conclusion. 1f c < u 1 c, then we
1 <8<2 (B. (Bp)),
(()())))((B))))
8>
{0},
$ = 1
d, E [1) (C((B.))
= and d" E
(2]. dB"
s 2
s<
SE (1,2)²
and specifically
0 c<C, S (B(b)) and C. (Bx) S dy < (Bx), uniformly on [gg, Byl. where
dB( 1<s<2
d,(Bp),
8> 1,
(0), ==1
(B,)
1,
= 1, and (B,)
{2}, ==2
(B,),,,
s<1
(Bx),,,
E (1,2)
C < 0 for and C² 0 for 1.
37

---

Published as a conference paper at ICLR 2026
H.2 TECHNICAL LEMMA
Assumption H.2 implies the following Lemma H.8 that will be used prove the uniform convergence consistency in Theorem H.5.
Lemma H.8. Let Pn. - log and Leb()) stands for Lebesgue measure and U1, U...... Un i.i.d.
points with probability measure M that satisfies Assumplion H.2, then for a given constant C3 > and for any 7 > 2 there exists E N and sequence én (7, C3. ()) > 0, en 0 such that
((An)) > 2(n + 2
n 2 no:
where Angy the event
Mn (Udn) Leb (Ln))
Un c. U, Leb (eb,,) 2= C3pl : Ca((1 26 cn))
inf
This result immediately follos from the proof the more general result by Mösching & Dümbben (2020, Section 4.3) which can be stated follows:
Lemma H.9. Let 8n > 0 such that on + while ndw// log(n)
(as oc). Then for every
yy > 2, there exists no no(y, 5n) and en = cal7, 5n) > O, Cn + 0 such that
P(nff
P inf {
Pr. ((hn) P(U)) Un Cu 2 8n 26 >1 2(n + 2)
n Z no:
where P(.), P-()) are respectively the probability measure and the empirical probability measure of the design points U1 U1,...... Un. that is
P(B) & / fo(u)du, (B
& 1 n Σ E for cu
and
en max cn//nn venn + (no,) 0,
where Cn A ylog(n + 2)/(n he= 1). The value ng is the smallest integer that satisfies Cn 1.
38

---

Published as a conference paper at ICLR 2026
H.3 PROOF OF THEOREM H.5
First note that for every Φ C, since Φ [Bar Bøl, then h ho E [By, By]. By assumption also have h' E [B., BR] for some 0 < BA < Bn < co. Let on be solution of (41), i.e. the LS estimate of Φ0. Then, being on minimizer, we have that for any direction A such that on d2 C for 5 2 sufficiently small, L(on + 8A) 2 L(Øn). Hence the directional derivative on along direction A satisfies
d
L( + +A)= [((m)) 0.
L(on +dA
lim 6.0
d8
6=0
Fix such a direction A R
+ E that will be selected later. We have
d
L 61)+
d
Σ
Y; h(0, (U.) + 82 (U:)))
d5
d8
8=0
6=0
>
A (U.))
N'n (U.)) (n@6n (Ui) Y.)
Adding and subtracting v/o(U.) = ((cbo(U))) we get
n
Σ (U
E
Au (U.) [n du (U.) o Gn (Ui)
(44)
In what follows, we apply (44) to a special class of perturbation functions A and write
1/2
||||n A ΣS(N))
||oa|| A
B B2, where on = +B,, Br)
The next Lemma H.10 is proved in Appendix H.4
Lemma H.10. For an integer m 2 O. let Dm be the family of all continuous, piece-wise linear functions on IR with at most m knots. Then for any fixed y >
(U.) (3n (U.)
Bm...A A
Sy (m)) A sup
4a 1))12((og for all m 2 0,
|
AEDm.
18
with probability at least
2n
The next ingredient for our proof is a result concerning the difference of two concave functions, which can be found in Dümbgen al. (2004, Lemma 5.2) and we report the proof in Appendix H.5 for completeness.
Lemma H.11. Let & satisfy Assumption H.4. There is a universal constant E = (L, ai) with the following property: for any & > 0, let < E min (b a, (1//), Then, for any concave function
sup e - Φ) 2 g or sup (E(a.))
(b-5)2
8,
implies
inf 3 0) > E/4 xE(c,0+6)
(0 - x) E/4, 16,0000]
inf
for some [a,b 6). More specifically we have l0 min
3x 1L
-
Now, we have show that one of our classes Dnn does indeed contain useful perturbation functions A. We denote with ø the unique continuous and piecewise linear function with knots in T n (U,, U,) such that on = on on T = {U,, U2.... }.}. Thus on is one particular LS estimator for do. The following technical Lemma H. 12 can be found in Dümbgen al. (2004, Lemma 3).
39

---

Published as a conference paper at ICLR 2026
Lemma H.12. For 0 S b ler
Mn(u):= = min Mnle, c u/. oE(o,b-u)
Suppose that p0n ~ 2 _ on some interval (c, + 6) C (a, bj with length 8 > Then there
function A Ds such that
On + AA is concave for some X > 0,
A (n) EA g
| 2 n2 Mn (6 6/2)/4.
(45)
Now prove the theorem. Consider the event
(x) supla 5.,1 140
Fnl
8
8a
for some (random) 6 that aim prove to be (1). Then we have 1/00 3al
|
do
v Tnl s (d0 0..l follows that
sup 88,
x(())= 2
8%
B
From Lemma H. replacing
8 8n
{ +
6
8
Br
there is a (random) interval [Cn, cn + 5n] C [a, b] on which 100 - Fal 1 48, 8 provided that
n is sufficiently large to guarantee that gl/a s a, so that min (b - a, (5g/aa 85///.
6-0
This condition comes from the fact that 5 E5/// that is 8, s
B.
1/0
8a)
Br.
Because [cn; +. ] is sub-interval of L/ length 6n, Lemma H.8 (which holds by Assumption H.2) guarantees that this interval contains at least one observation U.. This implies Lemma H.12. For any
A E DD define IA- = {i (U)) < 0}. Define also J = {i : (U;) Z. (U,) > 0). Using that M E Br, BA) with BA Ba > (which comes from Lemma H.7) have that
0 < (,0 3m) < h()))) h( < Bn ( - Fn) points U; with i E J,
B, (00 )n) < h( h(@w) < B, )n) 50 on points U, with e J
and as a consequence, using that 0 < h E [B Br) we have
0 << 3,, - (.) ( - h(,a)) ) s (00 tn) on points U4 with J, Bi ).)) < N' (( k((w)) Bi (du 2n) points U, with i e J. (46)
40

---

Published as a conference paper at ICLR 2026
Recall that o% (Br, B,) By the definition of (6) and Lemma H.12, there is (random) function A E Do such that
(6) E A (U.) H²,,. (U))),
| 1oall
(44) E A (U,) N' (on (U:) h(6o (U.)) h(ē,, (U.))
A |nl onl
Σ iELANJ
+
Σ
iElanJe
ieigns
iEignde
(46)
2 (|A1ll/lou11)-
Σ A(U,)(0o(U.) - (n.l)) + BB, sergn
Σ
A(U)) - Gn.()))
iElANJ
+ B
Σ
A(U))(o(UU) - -x,(1))
Σ A(U.)(o((U)) - Tn(U
XETANJ
iElSnJ
(45) 66
8 [[A
D Σ
A(U))++B
Σ A(U,)+
4BA
KETANA
KEignJ
+B
Σ
A(U:) + BR
E A(Ui)2
iElanJe
nErgnee
8
8
||
|lon|l1 B
4B
(15)
6
(n,M (8n/2) /4) 1/2
8%
||oa|l -BB.
4u
Consequently,
4B, 2 11n1115 (n.t (8n/2) /4) /4) 112
(6).
Now consider the event m in Lemma H.10 and the event Ann in Lemma H.8. For > 4 define
Gn, = An,y n B6,
which holds with probability at least 1 1 1-2n²=7 In Gn,y we have
E s 4B 3,, 3,
(())))))) (6) 4Ballon ((C_
< 4B IB, (C.x/8)~11/) (1=3(
where we used that o(1) is positive quantity appearing in the denominator. More precisely we have that
sup sup
(.)
> E
C (6) 2 -1oon (C.x/8)/² (1)gn)
8
then with probability less than 2n2-9 we have sup 6-5m] 11/0 - 1.l 2 C8 provided (by Lemma H0)
(4BB)) -10x -BB (C)/8)1/
1/2 270V7
More precisely, the condition on 6 is that 66 2 max 88-a (4B,) *lloa|l BB </8)1/2 where
70
7 4. Using that
BBr BB) T and 80 I (from Lemma H.11), this condition becomes
4 41t L B
4 4vTBA70
B3 B
E > max
B (C.u /8) 1/2
41

---

Published as a conference paper at ICLR 2026
H.4 PROOF OF LEMMA H.10
Assumption H.3 implies the following inequality
E S ((U.) 1 ( (U:))
11²
P
n <
exxp
(47)
||
20
for any function { with || > 0 and arbitrary 2 0. Indeed, since 0 < B, S n'n (U+) I B
we have
(U.) S B, M ((U)) E + ((U)) E,,
(48)
iE!
iET-
where I = {i: (U,) E, 0} and 1s {i: 5 (U,) E, S 03. We get
El 5 ((U,) N' W(O,, (U))) !?
P
P
BR Σ (UA)
E. + Br
E{(E)) (UU)) E. 2 nlllllnllon11
iEl
}
$ <exp (-n|(S1m/lon))
exp
B
(U.) E, B Σ ((U,) E;
iC!
ietc
II
TE
eexp
BBa (U,) [.]] II
E
eexp
(B,S (U:) F.]]
VEI
/E/-
S cxpp (-7(((/((a))))
II [exp (B]s² (2)))222]] II iEfc
exp (B) (U:) /2]
< (xpp-nn|<ilzllo) exp [1o, 1111002222
exp (-1) (20=))
where we used that 1 + |loa 1|22200 /2 is maximized at x n/(o>|lox|)) II). Equivalently get
En ((U)) (UA)L,
2n )
112
S exp
Sexp
2
and
E ((U)) (U))
17²
P
21
< 2eex
1111l
20
For sissk k S n, let
1 (4) = 1 tu [,, Un} u u- U,
Uk u
and (u) = 1 fu E Ub]
U, U,
Up U,
if U2 < Uk. Otherwise let 1 (u) = 1 fu= U and (2) (w) = 0.
This defines collection & of at most n different nonzero functions c/p). Then for any fixed yo 2, (47) implies
2 P Sn S (log 2 n28/2
where
Σn 5 (U,) 1 (6n (U.)) E,
Sn == max CEO
1kclnn |oa|
42

---

Published as a conference paper at ICLR 2026
Plot of (1)()) and (220
5/200 (0)
())
Figure 1
For let G.(()= = ||<||= Σm= (U.) E... Then by (47),
P P(s, Sn (logn)))
S
Σ p {IGn(S)> 2[G]())22000lll Too(log))1/
(49)
CEo
S 2n
exp
(-12 log(n)/222
4-76
2n
7 0 as n + 00
because %o 2. Recall that Dm is the family of all continuous, piecewise linear functions on R with most m knots. For any A E Pm, there are m < 2m 2 disjoint intervals on which A is either linear and non-negative, or linear and non-positive. For one such interval B with M, (B) > 0 let (UI...., Un n (U,...., U.). Then
(w) A (Ux) Go (1) + (U;) (u) for u e (U,, Uk]
(w)
Piecewise Linear Function Dr,
Knots
Plot of ci, SE and A(t)
A36 Kincss
10
NB
113
231 6n
En
Figure 2
Figure 3
43

---

Published as a conference paper at ICLR 2026
This shows that there are real coefficients X1. A and functions {1,, (1....., .., Sam++ a in + such that j= Am++1
XyGy (U1,..., Un]] and C for all pairs (i, k). Consequently,
E A (U (UD)
E 4m+4 j=1
1yl1 Ei= So (U (U.))
| |nll
Emm X3 l1sal1))) 1/2
|1
Σ Am++
P4 |1Gill
1/2 Sn
4m+
X3 (1ss
2F=1
S (4m + 4)
The last inequality is due to Cauchy-Schwarz inequality
1/2
1/2
4m
4m+4
1m+4
M x1=
Σ
X3 11yl11
Σ j=1
12
==
Thus by (49) we have that
Σ A (U.) (U
21 2n 1-22
P sup sup m20 AEDm
< (log 1/2
A (m + 1)1/2
Setting y = 2% we get the result.
H.5 PROOF OF LEMMA H.11
We divide the proof in 2 parts. Part A: (6- (1)) 2 for some to E [a, bj. Part B: (6- 2 for some to E [a + 6,6-)..
A
Suppose that (6- Φ) (1o) for some to b). Without loss of generality let t, S (a + b)/2. Define the linear function
1 (to) σ(-) { ④ (to) + (tx) (.
if a > 1,
Define the concave function 4 = θ T. Now, note that by Assumption H.4 we have
1 s Llt to /a,
(50)
Now, since by assumption suPrela.d]
6 0 2 & we have
(tt.) = (tc)) ((to) 2
(51)
Now let 0 < 8 (b a)/8
Step 1.A. Since & is concave, it follows that if & (to + +0) e/2 then, joint with (51),
+ 2 e/2 on [to: to + 6).
Step 2.A. Now assume + (t, + 8) < E/2. By concavity of + we have
& (to)
(8 (t.+)) = (t. +6) s 8 +
< 12-g/2 ((to))
<E/2
28
Consequently, for t 2 to 38
((t) <
(t, + + + (t (t-t-
8) (t,, +
4 concave
<E/2
226
<-8-1E/2
E/2 288 (g/2) E/2
44

---

Published as a conference paper at ICLR 2026
Step 1.A + 2.A: & 2 2/2 or +b 2 E/2 some interval J C [to, to + 46] with length 6. Using this fact and (50), we have that E J
or
is greater or equal than
E/2 - - to) to) 2 E/2 - L(48) /a,
1/a
which is greater or equal than E/4 provided that 5 $ 1 47.
Part B
Now suppose that (o 5) (to) 2 for some > 0 and to E [a + 6, 6]. where 0 < 8 (b-a)/2. By Assumption H.4 and concavity both Φ, á there exist numbers 7
such that
<(t) 2 d (to) + 7 to) L - /a.
and
2(1 S (1)) + +7 -1-16) (6))
Thus
to) L - tol /a 2 L8a
for all L in the interval [l,, to 5] or |4. 6, lo). depending on the sign of 7. Moreover, 1/a
g L8 / 2 g/4, provided that ā <
3 12
45

---

Published as a conference paper at ICLR 2026
1 REMARKS
1.1 REMARK ON ASSUMPTION 3.2
In this section, we discuss sufficient conditions under which Assumption 3.2 holds. Under twice differentiability of vh, the strong concavity of rev, (- |p-<) uniformly over p-4s is guaranteed there exists value μi 0, such that - Op rev;(p p-i) Z pi for every p E P.. uniformly in p-i P-i. Uniformity in p-: P-; means that μ4; does not depends on p-j. Here give some examples where this condition satisfied.
(1) Linear demand models (Li et al., 2024). In this case rev,(p p-:) = p(a, - 3,p + 7. p-.).. and 0% rev p-,) 23; >
(2) Concave demand models. If s/s such that v/ 2 Bug for some By: > 0 as in Assumption and is concave, which implies Op rev,(p p-;) = p-(--1p+7% v p-i) B.pr -B p-.). then
- Ra revi(p p-i) = 20% + 7. p-i) pr BBpp + % p-i)
2 (- + 7, p- ) 2 2B >
Note that requiring concavity of s is equivalent to requiring 1-concavity of th, then, by the inclusion property of s-concave functions, any (positive and strictly increasing) s, s,-cocev U with 2 1 satisfies Assumption 3.2.
(3) s-concave demand functions. Suppose that vi satisfies Assumption 3.1 and Assumption 3.4. Then, by Proposition 3.5, vi is s,-ooncave for some 8; -1, and by Lemma B.1 this is equivalent to e/ < (1 - s; (w))) This implies that
rev p-i)
= =2 + 7: p-i)
p-s) 2 201(-Bipp + 7: p-i) - -3:((1- -101:///00----0pp-//////a------- 7. p-:)
- + p-;
and since v 2 B > 0 sufficient condition is that
2 3. =- p-1) C2,
for some constant C; > 0. Note that since v//v/2 is non-negative, for 2 1 the condition is trivially satisfied with C, 2, indeed this condition coincides with the case studied before for concave demand functions. When E 1) the condition becomes
d p
15 3,p + 7 p-s) -K,
{log owh (-ppp + 7. p-1)] -3pp dp
the( 3,p 7
where we set K; condition such that the inequality holds is that the hand side is negative too, i.e., if C, S 2, or K, > 0. For example, suppose that th; is O-concave (i.e. log-concave). that is t) = の for some increasing concave function di, where Φi needs be increasing in order guarantee that v/ is increasing. The condition becomes
(11)) Note that the left-hand side is always negative, then, necessary
2- 2-C,
d dp
B-po'--B.pp + 7/ p-1) = = log w.(--1p+++ v. p-+) S K,,
and it's easy to see that any di (x) = az for 0 sufficiently small works. Indeed the condition
becomes p & K2/(3,) for all p P., which holds as long as K2/(8,)) 2 P:. or K,/ (B,P.) Another example is (x)) -1/(x + for b sufficiently large, indeed the condition becomes
(-App-7 p_.+ 5 K./ 8, or p < K for some K; (b) > O, and must by such that K 2 P..
46

---

Published as a conference paper at ICLR 2026
1.2 REMARK 4.1 ON THE COMMON EXPLORATION PHASE
To highlight the importance of a common exploration phase, demonstrate that seller has an incentive to extend or shorten the exploration phase. If firm prolongs its exploration phase, risks incomplete learning of its model parameters (Keskin & Zeevi, 2018), leading to inaccurate parameter estimation and, consequently, a loss in revenue. Conversely, if firm shortens its exploration phase, may achieve consistent estimation but at the cost of higher regret due insufficient exploratory data. For a better illustration, consider a scenario where firm extends its exploration phase to 7' > while all other firms use phase of length т. When firm estimates its parameters using data (p")),) herr', the data from times T + to r' are no longer iid. In this later period, all other firms have already started their exploration, causing the prices {p 1p tp=+t=rr,,,.,"" be dependent (t)
on the earlier data {p_) {p-; Jt This dependency result in inconsistent parameter estimation and a loss of efficiency for firm i. Conversely, if firm i opts for shorter exploration phase than т, may achieve consistent estimation, but the reduced amount of exploratory data could lead to lower efficiency compared to firms that adhere to the full exploration phase.
1.3 REMARK 4.2 ON THE NEED FOR TWO DIFFERENT PHASES FOR MODEL ESTIMATION
In principle, could estimate (0:, 1h,) jointly using the full exploration phase. For instance, Balabdaoui et al. (2019) employ a profile least squares approach to achieve L convergence for the joint LSE of (0., th:) based on the data {v, ()))) However, in our context, L convergence alone does not suffice to establish an upper bound on the total expected regret. To elaborate, let (0,L. (bg denote the joint estimator proposed in Balabdaoui et al. (2019) based on the data
((v) (0) (()))))rr Their result applied to our setting gives the following I convergence rate:
(Jp (W (pp, 0.1S)) v. 0.1)) dD(p))
= =0p (T-13).
Here, the convergence is measured with respect to the measure ②, which governs the distribu- tion of prices during the exploration phase. Consequently, the I distance between (0;, 1/4) and (0.LS, , ( can only be evaluated for prices distributed according to Z. However, during the exploitation phase (L 2 + 1), the distribution of prices p(!) may differ from 2, making it impossible evaluate the performance of the estimators during this phase in an L sense. A uniform convergence result, which does not depend on any specific price distribution, solves this issue. However, achieving uniform convergence of the form
SuPpEP
(!)))) v 0.))
(52)
challenging when 10. (T.)) are estimated jointly. To overcome this difficulty, our approach is first estimate O, and then, conditional this estimator, separately estimate via using independent dataset. This two-step procedure ensures conditional independence and yields consistent estimators, addressing the difficulties of the joint estimation strategy.
47

---

Published as a conference paper at ICLR 2026
J SIMULATIONS
J.1 CONTRACTION CONSTANT VARYING REGIMES
We evaluate the performance of Algorithm in the sequential price competition model with N e
{2, 4. 6) sellers. Each seller i E N {1, (1. N sets prices supported on P = [0. 3|x X We examine how convergence behavior changes the contraction constant Lr varies -specifically, when is close to O, near 0.5, or approaches 1.
Recall that the contraction constant of the Best Response operator is
17:l1
Lr = sup seN
5
lmlll, which simplifies to Lr = supteN Bi In our experiments, we take
when the link functions e) are log-concave (see Remark 3.8).
(1(2) ( i= 1
where the cumulative distribution function of a standard Gaussian random variable. Since is log-concave, the simplification applies. We now identify the parameter regimes for 8 that yield Tr and Lr R
In the extreme case Ir 0, we must have B, t 1 for all N, which forces % + 0 component-wise.
Case Lr + 0.
Case 2: Lr f 1. To approach the opposite extreme, Lr 1, consider
sup iEN B.
sup
< 1, such that +1 =1 VieW.
Without loss of generality, fix i 1. By the Cauchy-Schwarz inequality,
Imllli S VN - 1/1//2.
So the largest possible l/m//1 occurs when entries of 71 are equally distributed. In that case, the
requirement becomes
VN - I 12 < $1.
Since 1/m1l2 VI Br. this becomes VN 1 II अ
B1. Squaring both sides gives
N N-1
(N - 3
Thus, Lr t as 31 4 V N-1 In particular, we have the following scheme:
N 2: 81 1 0.707 = Lr 1 1,
N = 4: 81 4 V 0.866
= Lr 1 1,
N 6: 8 8 0.913 - Lr 1
A summary of the two extreme cases can be found in Table 3.
Simulation design. Given the discussion above, and the table in Table 3, for each N E (2,4, we run simulations under three representative values of 3e, yielding total of 9 settings:
N=2. 8, = 0.71, 0.84 0.97.
N=4. 8, 0.87, 0.93, 0.99.
N=6. B, 0.92, 0.955, 0.99. 0.99.
48

---

Published as a conference paper at ICLR 2026
Table Extreme cases for B and corresponding behavior of Lr.
Case
Condition on Bi
Condition on %
Ir 40
B, t Vi EN
Imill1 0. Vi E
Lr 11
81 4 V NN-1/N
Ti 1 1//NNN-- N(N-1) for E N (1)
N =
31 + V
71.2 1/v2
N =4
31 | V
M 1/VTE for = 2, 3,4 ny 1 1/v30 for j = 2, 3,6,
N =6 -6
B1 & V
In all experiments, demand noise follows Unif[-0.05, 0.05]. The common exploration phase has length? 7 and the length K; of the first part of the exploration phase determined using Equa- tion (14) with 8; = 1, B, = 1. During the first phase of the exploration phase, the values of p(0) are samples from multivariate Gaussian with mean
P: + + m
P:
P.
Σ diag
2
KENV
iEN
For each horizon 7' {100, 400, 800, 1600, 3200). we apply Algorithm and repeat the simulation 30 times to obtain averages and 95% confidence intervals.
The results are displayed in Figure 5, and a log-log version to highlight the convergence rate in Figure 6. As expected, convergence accelerates the contraction constant approaches 1, in line with the intuition highlighted in (9).
J.2 DIFFERENT EXPLORATION PHASES ACROSS SELLERS
In this experiment, we replicate the setup in Appendix J.1 but relax the common exploration phase assumption in order test the robustness of algorithm. An illustration of misaligned exploration phases is provided in Figure 4.
seller
selling
Exploration phase
seller
End of explocation phase
Explotsation phase
seller
End of selling borizon
Private exploration estlimating
seller 4
Private explomtion for estimaring ys
Comman Exporattion
Non common plase
Common Exploitation
Cocmenss
Figure 4: Illustration of our policy (Algorithm 1) with N 4 sellers in sequential price competition under nonlinear demands. For each seller i E 2,, 3,4. in their exploration phase (dotted line) of length т₁ they offer randomized prices following their distribution 9, Within the exploration phase, each seller has private phase for estimating 0; (blue box with dotted border), with length 7,K; and private phase for estimating v/; (yellow box with continued border line), with length T.(1 - rg). The i-th seller's price experiment ends at period t т, (black circles). Subsequently, in their exploitation phase (represented by the continued black line), seller offers prices based on the estimators generated in the exploration phase.
We set the exploration length of each seller as
Thuse + 0g Thusey W4 Unif(0.25, 0.75)
49

---

Published as a conference paper at ICLR 2026
where Tbase / The allocation parameter K; for the first part of exploration is computed using Equation (14), with 7 replaced by тą and fixed constants E; = Bi = For this simulation, we set 3; 0.8 for N 2, 3; 0.92 for N 4, and B; 97 for N 6, which satisfy Assumption 3.6.
During the exploration phase, the prices pj distribution N (mm,, σ;) with
(+) are sampled independently across sellers from Gaussian
+ Pi
P. P. iEN.
m4
0
2
For each horizon T E {100, 400, 800, 1600, 3200}, we run Algorithm I and repeat the simulation 30 times, reporting averages and 95% confidence intervals.
The results are reported in Figure 7, together with log-log plot in Figure 6, which illustrate the convergence of prices to the Nash equilibrium and the decay of regret.
As anticipated, the estimation of i deteriorates, in line with the intuition of Remark 4.1. Indeed, the horizon T grows, the exploration lengths т; increase for all sellers, which enlarges the non- common exploration phase (see Figure 7). Consequently, a larger number of price vectors (t) no longer i..d., making parameter estimation increasingly inconsistent. Nevertheless, despite the adverse effect the estimation of vh both convergence the Nash equilibrium and regret performance remain robust, with empirical regret rates matching or even surpassing the theoretical benchmarks of 1/7 for equilibrium convergence and 5/7 for regret.
J.3 ROBUSTNESS TO MISSPECIHICATION OF 8,.
In this experiment, we replicate the setup of Appendix J.1, except that we fix N = and set 3 = 0.9. We again take (u) (2u/t) for i 1.2..... N, where & denotes the c.d.f. of standard Gaussian random variable. Since t is log-concave, each th is O-concave, that is, 8; = 0. We then Algorithm under five different shape parameters 8 (-2.2, -011, O, 0, 0.2). As shown in Figure 8, this misspecification of 8; has no visible effect on either the NE convergence rate or the regret convergence rate. The small variations in the estimated slopes reported in the legend of Figure are plausibly due to maite-sample noise (T = 1600).
50

---

Published as a conference paper at ICLR 2026
10
6.1l
Ees 10
1p"
Tolai Expected Regget
0.2
by
11005
by
170
0.4
by
1.001
Ly 54.1
D
0.2
10002
0.2
012
1.3
11000
11.
0.50
20002
0.25
2100
0.2
2,000
1.2
500
T
Figure 5: Performance of Algorithm in sequential price competition with N E (2,4, 6} sellers for different values of the contraction constant Lr-
log 1p
p'lla
log Total Expprrted Regret
3.0
-00
-1.
kgT
kg
Figure 6: Log-log performance of Algorithm 1 in sequential price competition with N (2,4, sellers for different values the contraction constant Lr- The slopes, indicated as m, of the convergence to NE and the regret are always smaller than the corresponding theoretical upper bounds (-1/7 and 5/7).
51

---

Published as a conference paper at ICLR 2026
-.Y
10
Total Expreeted Regret
0.25
8003
014
50
7007
30.00
3300
T
22)
log Total Expected Regret
m.20
-10
6.0
7.0
kgg
Figure Performance in the different exploration phases.
180-00
NX Centrpper
Begue
Choommpeca Sigu
1000
Liggt Stowe
45
Figure 8: Log-log performance of Algorithm in sequential price competition with N = sellers for different values of misspecification s; O, specifically {-0.2, 00.1, 0, 0.1, 0.2). The slopes, indicated as of the convergence to NE and the regret are close to each other. The small variations the rates can be attributed to the finite sample experiment (T 1600).
52

---

Published as a conference paper at ICLR 2026
K
ADDITIONAL FIGURES
seller
Start salling horizon
Common exploration phase
seller 2
Common separation pariod
Common exp
seller
End ling horizon
Private exploration for estimeting
seller
Private expioration for astimating V:
Figure 9: Illustration of our policy (Algorithm 1) with N 4 sellers in sequential price competition
under nonlinear demands. For each seller E 21, 4), in their exploration phase (dotted line) of length they offer randomized prices following their distribution D. Within the exploration phase, each seller has a private phase for estimating 0g (blue box), with length TK; and private phase for estimating dù; (yellow box), with length 7(1 Kz). The seller's price experiment ends at period t (orange circle). Subsequently, in their exploitation phase (dashed line), seller offers prices using the estimators generated in the exploration phase.
53

---

Published as a conference paper at ICLR 2026
L EXAMPLES OF S-CONCAVE NON-DECREASING FUNCTIONS
The notion of s-concave functions generalizes concavity (s and log-concavity (which holds for 0). The class of log-concave functions has been extensively studied: see Bobkov & Madiman (2011); Dümbgen & Rufibach (2009); Cule & Samworth (2010); Borzadaran & Borzadaran (2011); I); Bagnoli & Bergstrom (2006). Since in this paper we consider a positive monotone s-concave function eb we first give some examples of monotone log-concave func- tions and generalize to s-concavity. Without loss of generality. we log-concave (and s-concave) CDFs t. indeed if & is monotone but its range is not contained in [0, 1], it is always possible to rescale v to consider it as CDE. Indeed if to is s-concave, the cp is s-concave for every e 0 because &i ((1 A)uo + Auy) 2 Ma (1b (uo) 1/ (ui); AA) for all uo, u, E U if and only
xb ((1 A)uo + ) 2 Mg (c. & (wv), C (u1) ; X) for all uo U, E U.
L. LOG-CONCAVE CDF
In Bagnoli & Bergstrom (2006) we find large class of log-concave CDF. They prove that if density function f is log-concave and continuously differentiable, then the CDF is also log- concave. This gives a way generate log-concave CDFs. Figure 10, by Bagnoli & Bergstrom (2006), presents several widely used continuous univariate probability distributions whose densities are log-concave. Except for the Laplace distribution, the cog-concavity of each density f can be verified by checking that the second derivative of In f(z) is non- across its support. For some families-such the Weibull, power-functiog beta, and gamma distributions-log log-concavity holds only for specific parameter values. The table reports the parameter ranges under which these densities remain log-concave.
Name of distribution
Support
Density function f(x)
Cumulative dist function F(x)
(In f()))"
Uniform
[0, 1]
x
Normal
(-o0, 00)
x²/2 2
-1
Exponential
00)
de -xx
e Ax
Logistic
(-00, 00)
2f)(2)
(I+e 1+e-ay2 x2²
(I+e 2)²
Extreme Value
(-o0, 00)
exp( --e-----
exp -e "}
-e-
Laplace (Double
(-00, 00)
2 -111
ex=
if x < 0
0 for x #0
Exponential)
1 20 if 0
Power Function
(0, 1]
crc-1
xf
1-c
(c 1)
2²
Weibull
[0,
C2 12- 2
1 1-e c x
1-c (1 + cx 22
(c 2 1)
Gamma (c 2 1)
00)
2 1
1-e
[(c)
Chi-Squared (c 2 2)
00)
(c- 2
*
2-c 2ra
2c/ [</2[(c/2]
1 2212
Chi (c 2
00)
*
1-c
2 21/2
Beta (v 2 1,
[0,1]
(1-x)--1
1-
1-
2/1 1)
((u
x2
(1-x)²
Maxwell Rayleigh
This is Chi distribution with 3 This is Weibull distribution with 2
Figure 10: (by Bagnoli & Bergstrom (2006)) Distributions with log-concave density functions (distribution functions marked x lack closed-form representation).
54

---

Published as a conference paper at ICLR 2026
L.2 NON LOG-CONCAVE CDF
When the density f is not log-concave, analyzing the behavior of the associated cumulative distribu- tion function F' is more complicated. Distributions with log-convex densities exhibit wide range of behaviors: some have log-coneave CDFs, others have log-convex CDFs, and still others have CDFs that are neither log-concave nor log-convex.
Figure 11, by Bagnoli Bergstrom (2006) summarizes, for each of these cases, whether the density and the CDF are log-concave or log-convex.
Name of distribation
Density function
c.d.f
Power function
log-convex
log-concave
(0 < c < 1)
Weibull
log-convex
log-concave
(0 < c < 1)
Gamma
log-convex
log-concave
< < 1)
Are-Sine
log-convex
neither
Pareto
log-convex
log-concave
Lognormal
neither
log-concave
Student's
neither
neither
Cauchy
neither
neither
Figure 11: (by Bagnoli & Bergstrom (2006)) Properties of distributions without log-concare density.
From Figure 11, we note that the CDFs of the Pareto, Lognormal. Student's 's 1, Cauchy are not log-concave. In the next section, we prove that they are s s---oiaal-concav for some s* < 0.
L.3 S-CONCAVE CDF THAT ARE NOT LOG-CONCAVE
In this section, present properties of s-concave functions and give some examples. In this Section, we will widely use Lemma B. without explicit mention, which states that if is a positive function defined in an interval (a, b) that is twice continuously differentiable, then f is s-concave iff
f f" (s - 1)(f') So in (a.
We start with the inclusion property. Proposition L.1. (Inclusion Property] Let f: (a, b) + (0, xo), a twice differentiable function. If f 8-concave, then f is s-concave for s S B.
Proof. If f is 8-concave, for S B it holds
[()))"(w + (s 1)((())( s ((v) ( (w)) < O,
ie., f s-concave.
As a consequence, log-concall concavity implics s-concavity for every S 0. An immediate consequence of the inclusion property is the following.
Corollary L.2. Let f ba, - oo), a twice differentiable function. Suppose that f is not si si-concave, but is su-concave for some so 81. Then, there exists s* E [So. s1) such that f is s-concave for every S s* and is not s-concave for every s s*
Proof. Let s* = sup(s: f. f" + 1)(')² < 0}. By the inclusion property, f is s-concave for all s* However, there not exists s* such that is s-concave, because it contradicts the definition of s*
Definition L.3. From previous Corollary L.2, we say that a twice differentiable function (a. b) (0, oc) is s* cenrival-concveeeee if
8: sup [f(u) (s (s (E(a.b)
8* = sup
55

---

Published as a conference paper at ICLR 2026
In this case, s" is called optimal-concave parameter.
In the following, prove under which condition s-concavity is closed under multiplication. Proposition L.4. Let f,g: : (a, - (0, oe) be twice differentiable functions
f and are s-concave with such that f' 2 0, then the product f-g s-concave. * f and are O-concave then the product f is O-concave.
Proof. The second statement is the rell-known result that the product of log-concare functions is log- log-concave; then, we only prove the first statement, which immediately follows from the equality
h- h²" + (s 1)(h)² = = (f- + 1)()))))+++++++ (a- + 1))-)))()))+222 + 2sf 9 .g'..
In the next sections, we first show the existence of some well-known distributions whose density is s-concave for some < 0 and not log-concave (i.e., O-concave). Then we identify class of distributions for which if the density f is s-concave, then the CDF F is p(s)-concave for fixed transformation μ that will be specified later.
L.3.1 8-CONCAVE CONTINUOUS DENSITIES
From now on, we assume that the PDFs that we consider are continuous. As we showed Ap- pendix L.2, many density functions are not log-concave, such as Student's Cauchy, Pareto, and lor-Normal. However, for all of them, we can show that the PDFs are s-concave for some s < 0.
Remark L.5. Note that for PDF such that {u f(u) > 0} R, it is necessary to impose O. Indeed for > O the function ((u) dg f(u) = fu), which is strictly positive on R. can not be concave. To see this note that, being f a density function, necessarily f(u) - 0+ as lul +00, and consequently, as [u] +oo we have ((u) - which is not possible if d is concave and strictly positive on R. The same applies to densities defined on any unbounded interval. This implies that if density defined in an unbounded interval is log- concave (that is O-concave), then it is Proptimal-concave However, when density f is compactly supported, there is no restriction on s.
The proof of Proposition L.6 is deferred to Appendix I.3.5.
Proposition L.6.
1. The Student's I-distribution PDF is (-o+-) ootiiallconcave where v > 0 is the degree of freedom.
2. The Cauchy PDF is (-1/2)-optimal-comcem (indeeeedeny of scaling and location param- eters).
3. The Pareto PDF is
optimal-concave, (independently of the location), where a+1
is the scaling factor.
4. The log-normal PDF with parameters (p,0²) is (- optimal-concave, (independently
of p).
L.3.2 S- S-CONCAVE CDFs AND SURVIVAL FUNCTIONS
Let F be CDF and F = F its survival function, and let f F'. When {u: f(u) > RR for similar reasoning as in Remark L.5, necessary condition for having o = d, a F or ò de o F concave, is that 0. In the following proposition,
find necessary condition on for which F and F are s-concave when {u: f(u)= > 0} = (),b) for a, b E IR.
The proof of Proposition L.7 deferred to Appendix I.3.6. Proposition L.7. Let f (a, b) (0, 20) be twice continuously differentiable function, and let Fu)) S f(t)dt for all æ (a,b) and define (() lima-sa (() and f(0
lim f (1) k =0=00, 0,
1) (f) 0, fa( and F is s-concave, then 1/2.
56

---

Published as a conference paper at ICLR 2026
2) f(b) 0. (b) = 0 and F is s-concave, then S 1/2.
In the following proposition, we prove that, under certain conditions, when a density function is s-concave, then the CDF and the survival function is u-connave for some p(s). The proof of Proposition L.8 deferred to Appendix L.3.7.
Proposition L.8. Fix a function / (a. b) + (0, oo) continuously differentiable, and F(u) = Sa f(t)dt all b) and define f(a) lim f(u). Then:
1) If f is s-concave on (a, b) with f() * 0 and s -1, then F is p-concave for all μ S 1
++I'
2) If J 8-concave on (a, b) with f(a) and 8 + -1, then F p-concave for all
J S
3+I'
3) If is monotone decreasing, then F is s-concave for any < 1.
The proof of Proposition L.9 is deferred to Appendix L.3.8.
Proposition L.9. Fix function f (a, b) + [0, oo) continuously differentiable, and let F(u) St d(t)dt for all E (a,b) b) and define f(b) lim fu)) Then:
1) If f s-concave on (a, b) with f(b) * and > -1, then F p-concave for all μ1 S 1
3+1
2) If f s-concave on (a.b) with f(b) 0 and + -1, then F p-concave for all
μ S 1
s+1'
3) If f monotone decreasing, then F is s-concave for any < 1.
The special case s 0 was proved by Bagnoli & Bergstrom (2006).
L.3.3 S-CONCAVE CDFs THAT ARE NOT LOG-CONCAVE
From Figure 11 we already know that the CDFs of the Pareto, Lognormal. Student's Cauchy are not log-concave. However, by our Proposition L.9 we immediately get that they are -optimal-concave for some s* < 0.
Corollary L.10. any μ S - where > the degree of freedom.
1. The Student's 's t-distribution CDF and survival function are pu-concave for
2. The Cauchy CDF and survival function are p-concave for any μ S (independently of scaling and location parameters).
3. The Pareto CDF and survival function are y-concave for any S (independently of the location), where a the scaling factor.
4. The log-normal CDF and survival function are with parameters (μ, o²) are y-concave for any μ S -==4, (independently of μt).
x²
From Proposition 1.8 (and Proposition I.9), if f is 1u" -ptoiiill--con it does not necessarily means that (and F) is s(x²) = (1 #1 -optimal concave. Indeed, the optimal concave value can be larger than s(n²). However, the class of distributions in Corollary 10,0,, we know that s" has to be < 0.
In the next section, we construct class of positive s-concave monotone functions that are not log-concave.
L.3.4 GENERATE s* -OPTIMAL-CONCAVE NON-DECREASING FUNCTIONS [0, 1). FOR
Proposition L.11. Let 0 10, + R be twice differentiable non-decreasing function (i.e., O' > 0) and strictly convex on set of positive measure (i.e., 8" > 0 on a set of positive measure). Assume that there exists s* such that
8" = sup(s: : (x) + s(O()))) < for all E (0. 1)).
57

---

Published as a conference paper at ICLR 2026
Define F(x) c Then F is -cconcave, but F is not log-concave (t.e., (F)())))) O for at least one x E (0, 1)).
Proof. We compute
Fxxx) (())))(())(()),
Hence
F(x)F (s (x(² = (10)+++ + (s
(x))))
=
Since (x))) > 0, the inequality
FF" + (8- - 1)(1F) <0
holds if and only if
(x +(0)+ ( O.
Thus the assumed condition shows that F is s" concaae. On the other hand, log- concavity come- sponds to the case i.e.
0" (x) + (0))²
=
(²(x) O.
Since 9 is strictly convex on a set of positive measure, we have ("(x) > 0 for the x in this set, so this condition fails. Hence F is not log-concave.
Examples of admissible A. We provide three explicit choices of strictly convex functions (0, 1) + IR satisfying
8 ((())) 00 for some s* < 0,
so that F(x) (xx) is 8 -oncavee but not log-concave.
1. Power function example. Fix a > 1 and set ((x) = x Then
f((x) = ox
("(x) = =a(a - 1)xa-2
and
(")z) ((')))( =
ar av [aa
1) sax
Since x² < 1 on (0, 1), sufficient (and sharp) condition is s < a-1
Hence F(x) = exp(xx) is
s* -ooccave for s* a-1 but not log-concave because (²(x) > 0.
2. Exponential example. Fix h and set ((x) ekr Then
8((x) ke
(²(x)= k
and
+"())+ + x00)+x00()))))) (0)))) 22 (1 + se kT)
Since ekz < eh on (0, 1), a sufficient and sharp condition is s & - Thus F(x) = exp(e is 8* -concave for 8* - but not log-concave since (x) 0.
L.3.5 PROOF OF PROPOSITION L.6
1(442) vFOl(S (5)
1+ 22 w+1
Proof of a). We have that f(x)
where 0s the degree of freedom.
We need to find the values of such that f. fll + (s - 1)(f²) < 0 which reduces to
2 1+
4x
V +
x² 1 4 -1 1) (1
-1)
2
V x+1)
1)
(1
x2
1+
v
D2
v
V
2
2 m-
(s 1--1
2x
1 w+1
1 (1+
50
58

---

Published as a conference paper at ICLR 2026
iff
4x2
(- (-2) )
(- 1++
x²
2 (
v + 1)
2 )
[+
x²
---'11
-1
1
2²
2
V
v
1/
4x²
V
1++1 2
x²
1+ -2
+
(8 1) v²
|
0
2
iff
4.22
1 4+11 )
(-
++1
-1
+ 1
2
++11
) (1+ x²
1+
+ (s - 1)
4x2
(- -u+11 11 2
(- 2 ) 0
v2
2
2
2
v/
v2
iff
4x²
V 1++1 1
2
1+ x²
4x²
V + 11
- 1
+ v
+ (s - 1)
2 0
1/2
2
v
v²
2
iff
U 1U+1 1
1 x²
(- (++1 1
4x2
-1 1
+ 2v
(s 1)4x²
2 0
2
v
2
iff
x² (-2(v + 3) - (s - 1)2(z + +1)+ + 2v) + 2v 2 0.
As long as the coefficient of x2 is positive the incquality is true for all x, i.c.
1 V V+1 1
-(v + 1-33--0 (s - 1)(v + +1++120 + (s (s= 2 +
8 85
Proof of b). The Cauchy has density (xx = (T7)-1
where To E R is the
location and 0 the scale parameter. We need to find the values of such that f. (--"+(s--)(('') < 0. However, since this incquality has to hold for all xr we can assume xo = O. The characterization translates to
1
x2 72
(-1 1)
2 7/2
1
2
2
8x
1
33
+ (8 11)
(-1)
2x
1
-2 2 72
x²
0
72
74
72
72
iff
2 (-1)
x 27 72
2
8x 2 + 74
x
-3
4x
x -3
1
+
+ (s 1) 7'
1 +
50
72
72
x2
iff
2
x22
Sx2
1x2
(-1)
1 +
+
+ (8 1)
g 0
722
72
74
iff
2x22
2
8x.2
2
+
+
(s 1)
0
72
74
iff
(- 2
8
2 72
x²
+
+
(s
1)
00
7
74
the incquality is true for all x as long as
1
6+ (s -
2
59

---

Published as a conference paper at ICLR 2026
Proof of f(x) garl. where Im > is the scale parameter and 0 the shape. We need to find the values of such that f. f" + (s 1)( which reduces to
x - 1)( 1) (a+ (a+ (s- 1)(a 1) 2(a+1)-2 < 0
iff
(=)) 1)(a 1)² 0 10
iff
1
a+1 (a +)) 1) 1)a² 50 3
20//2 exp (- ( where 2, a > and μ R. Since
Proof of f(x)
the
0v2n
(In =
problem reduces to prove that f(x) = exp
/ is s-concave. Note that
1
(In -1)2
1
(In - -1)2
In
f())
x2 exp
+ exp
20²
x
20
xO
1
(-
(In 11)2
In 1
x2 exp
1+
20²
σ²
u²
(o + u)
02z² exp
202
where u = In and
("(x)
x22 exp
1
(In 11)2
In 1
In
p
+
202
0²
x
(In x 11)2
x
20
2
2x
+
z-
0²
exp
20²
x
(In x - 14)2)
In
In
22 exp
+
20
σ²
(In 11)2))
2
la
o
exp
202
x3
2
u2
2
[1
+
1 +
0²
3
exp
20
02
exp
202
x
1
u
[(02 + u)w
0² + 20 + 20221
423
exp
20
1
1u2² + 30 u 02 - -2021]
exp
o423
202
We need f fd + (s 1)(f²)2 < 0, that is
exp (
22
-1) exp (- 2²
1 + 30 u - 02 - 20²]] +(s -1) 04g
(-0²)
(0" + u)² 00
iff
2 +302 u 0²(1 - 20 (s - 1) u) 50
60

---

Published as a conference paper at ICLR 2026
iff
su²² + -1 (s 1)0² 1
iff
su² + 11++2s0000 so4
sot + 0² uo
0² s 0.
The determinant A = = (1+ 100---458000 48 - 0² 2 4s). Then have s-concavity for all 8 5
L.3.6 PROOF OF PROPOSITION L.7
Proof. We have that F f' + (s - 1)f² s 0, which implies f'(u) S (1 8) ((w)
for all u.
F(u)
(a,b). b). By sign conservation theorem this implies that (a( S (1 8) lim
[(w)
(1
F(u)
s) lima-+a f((w) (1 s) limu- 22) = (1 (a) Since fa # 0 then f(
f(u)
and then 1 < (1 - s)2 which implies - 1.2 Similar proof hold for F.
L.3.7 PROOF OF PROPOSITION L.8
Proof. We need to prove that f' (n- 1)ʃ² S Using that fe-1. f" is non-increasing (because (d, o f)" s Oie. (d. o f)' = f is non-increasing) we have
(u) F(u) = S(u) [u] [" s(I)dt S [ (m) l (-(())(())(())))))) [(u)
(u) f(())
1
fstt (u) f (a)
f(u)f=-11
s+1
If f(a) * then, being -1 we have
f'(u)
fotl (1) pot (a+ (a)
f(u) +1
[lu) S f(u)se-I(u (u)
<
[(u)
which implies 0 2 F.F.F. f f F. f (n- 1)f2, which proves 1). For 2). being f(a)
holds with the only assumption that s * -1. For point 3), notice that since Fs-1 is monotone decreasing for < 1, then Fs-1 f' is monotone decreasing, but pe-1
note that ('(a)
T(a) Fl)) < f(x)
++1
F (1) du (d.(F(u))) which implies that F is s-concave.
L.3.8 PROOF OF PROPOSITION L.9
Proof. We need need prove that -FS + 1)ʃ² < O. Using that fa-1, I' non-increasing we have
f')) F(u) (u) f((u) /' f(t)dt 2 f(u)fa-1(u) / (-)()))))))(
f(u)
f(u) fu-1(u)
1
f (b) f(+t(u))
f(u)fs-1(()
++
(bb # 0 the, since s 11, we have
f'(u)
fst1 fst1 (2)
f(u) +
F(u) f(u)fo-1uul
f(u)
which implies 0 0 -F - + (μ 1)f2, which proves 1). For 2), being f(b) 0.
we have that f(uu] (u)) 2 --((u holds with the only assumption that * -1. For point 3), notice f(u)
=+1
that since f- is monotone decreasing for < 1, then - f' is monotone decreasing, but
- (w) (u) du (d))), which implies that F is s-concave for any 1.
61


Reviews:
[{"review_id": "qTrUdKCNLV", "reviewer": "Reviewer_neHp", "summary": "This paper studies price competition among multiple sellers with public price information and private demand information. Under monotonicity and s-concave shape constraints on the demand function modelled by the single index model, the authors show that, using their proposed algorithm, the prices converge to NE at $O(T^{-1/7})$ rate and each seller incurs a regret of $O(T^{5/7})$. \n\nThe algorithm follows a simple two-step approach, where all the sellers explore for a short time period to gather data for estimation, and then exploit with the estimated prices. The authors also argue that the convergence to NE is closely related to sublinear regrets of individual sellers.\n\nA key observation in the proof is that the monotonicity of the virtual valuation is equivalent to the s-concave property (Proposition 3.5). Furthermore, the s-concavity of mean demand also guarantees the strong concavity of the revenue function.", "questions": "- The algorithm relies on the knowledge of $s_i$. I understand that this limitation is acknowledged in the future direction section. It would strengthen the result significantly if this assumption can be relaxed. Can the algorithm potentially be improved to allow an estimation of $s_i$, or maybe it can be adapted to select from a grid of $s_i$ values (e.g., Lepski method)? More exploration on the possibility/challenge of this issue would be really helpful.\n- Similarly, $[\\underline{B}_i, \\bar{B}_i]$ is required to be known. Can the authors add some brief explanation/justification of this into the main text?\n- The authors comment on the tightness of the result (Line 432 - 444) by comparing with related result. Can these argument regarding lower bound be more rigorously stated? Especially given the concavity of the revenue function, one would typically assume a faster rate like $O(T^{-1/2}$ in classical literature. What is the key insight that drives the current regret bound?\n- Assumption 5.1 appears unnecessarily abstract. What scenarios does it cover beyond sub-Gaussian?\n- A short discussion on how the presented work relates to algorithmic collusion and potential societal impact could be practically meaningful", "limitations": "", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "- The conceptual relation of virtual valuation and s-concavity is elegant and useful.\n- The demand model is single-index, and its estimation leverages semi-parametric least square regression, which is of theoretical depth.\n- The overall writing is good; the presentation of assumptions, results, and algorithms is clear.", "weaknesses": "- The motivation of the proposed setting is not particularly strong, as it assumes that all the sellers invoke the same pricing algorithm. This was justified using some factual evidence from the practice at some area in Colorado but broader applicability is not well addressed.\n- As mentioned by the authors, the convergence to NE and sublinear regrets are closely related (Line 240-266). Combining with the previous point of all sellers using the same algorithm, it is hard to see how this result differs significantly from the setting without competition, e.g., the prior work by Fan et al. (2024).", "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": "8kp68uFJ0K", "reviewer": "Reviewer_TM1z", "summary": "The paper considers a setting where sellers can observe each other’s prices but can only see their own demand. All sellers use the same learning algorithm, and the authors prove that each seller can achieve sublinear regret while the prices collectively converge to a Nash equilibrium. The theoretical results are both novel and solid, though they rely on several somewhat contrived assumptions. The paper uses simulations to validate the findings; it would be even better if the authors compared their approach with other algorithms.", "questions": "See above.", "limitations": "", "rating": 4, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "The conclusions of this paper are novel and valuable. The study of demand learning under s-concavity extends the frontier of existing research on this topic. Moreover, the proofs are rigorous and nontrivial, making it an excellent theoretical contribution.", "weaknesses": "1.\tIn lines 54–56, it would be helpful to briefly explain how this assumption fundamentally differs from the previous linear model and what additional technical challenges it introduces in the analysis.\n2.\tWhy don’t we restrict $\\gamma_i \\ge 0$? An increase in others’ prices usually leads to higher demand.\n3.\tIn line 252, why is $\\Gamma$ assumed to be Lipschitz? Is this an explicit assumption, or can it be derived from earlier conditions? It would also be helpful to clarify under what circumstances this assumption holds in practice.\n4.\tSection 3 contains numerous assumptions but lacks illustrative examples. For instance, the authors should provide some common examples of functions that satisfy s-concavity. Listing assumptions without explanation raises concerns about their practical relevance. In reality, demand functions rarely satisfy such properties. It would be valuable to discuss how regret behaves when these assumptions are violated, for example, how regret depends on the parameter $s$.\n5.\tThe term “optimal” in Remark 5.6 is not precise. The paper lacks a lower-bound analysis, which is essential for assessing the tightness of the derived regret order. As mentioned in the experimental section, the observed rate in simulations is faster than the theoretical one, which likely stems from a loose upper bound. In such a case, the parameter can only be considered optimal with respect to the construction of this upper bound, rather than being a generally optimal $\\xi$.\n6.\tThe experimental section lacks comparisons with other algorithms. Even if alternative methods, such as those assuming a linear model with possible misspecification, are included, such comparisons would highlight the value of the additional assumptions introduced in this paper.\n7.\tIt would be helpful for the authors to explain why exploration and exploitation are treated separately, rather than adopting optimism-based algorithms (e.g., UCB-type approaches) that integrate the two.", "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": "CdOnTHR6SG", "reviewer": "Reviewer_1Gqn", "summary": "The paper studies price competition among multiple sellers over a selling horizon of $T$ periods. Each seller’s demand depends on both their own and rivals’ prices. Sellers observe competitors’ prices but not competitors’ realized demand. The paper proposes a dynamic pricing policy that converges to the Nash equilibrium prices.", "questions": "See Weaknesses.", "limitations": "", "rating": 8, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The paper proposes a novel semiparametric pricing policy for nonlinear mean demand. It adopts a more general framework of $s$-concavity.\nThe paper also establishes an upper bound on the total expected regret and analyze the convergence to the NE.", "weaknesses": "Major comments:\n\n1. In Assumption 3.1, the constants $\\underline{B}_{\\psi_i}$  and \n\n$\\overline{B}_{\\psi_i}$ are assumed known. How do sellers obtain these values in real-world application? You can also provide some references to justify this assumption. \n\n2. In the exploration phase, price is randomly chosen. Can you provide some practical examples or some references to justify it?  \n\n3. In the experiments, when estimating $\\phi$, how is $\\mathcal{H}_i$ in Equation (11) set?\n\nMinor Comments:\n1. Line 59: There is an extra comma after “own price.”\n2. Line 75: “Early work Kirman (1975)” should be “Early work (Kirman, 1975).”\n3. Line 88: “economics literature Birge et al. (2024); Li et al. (2024)” should be “economics literature (Birge et al., 2024; Li et al., 2024).”\n4. Line 96: It seems missing some words between “symmetric p(t)” and “Brillinger (2012)”", "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": "nhmWjwxUFe", "reviewer": "Reviewer_apYP", "summary": "The paper studies a repeated price competition game with N sellers over T periods. In each period, sellers post prices simultaneously and publicly observe the joint price vector, but each seller only observes its own random demand. Seller i’s mean demand is modeled as a monotone single-index function $,\\lambda_i(p)=\\psi_i(\\langle \\theta_i, p\\rangle),$ with $\\theta_i=(-\\beta_i,\\gamma_i)$, $\\beta_i>0$, and $\\psi_i$ unknown, increasing, and $s_i$-concave. The domain of the index is $U=[-p_{\\max},p_{\\max}]$, and noises are sub-Gaussian. Each seller’s goal is to maximize revenue and minimize a regret metric defined against a dynamic benchmark best-response $\\Gamma_i(p_{-i})=\\arg\\max_{p_i\\in P_i} p_i \\psi_i(-\\beta_i p_i+\\langle \\gamma_i, p_{-i}\\rangle)$ while treating rival prices as fixed. The policy uses a common exploration of length $\\tau\\propto T^\\xi$ to estimate $(\\theta_i,\\psi_i)$ in two stages via centered least squares (for $\\theta_i$ under elliptical designs) and shape-constrained nonparametric least squares (for $\\psi_i$ with monotonicity and $s$-concavity), then an exploitation phase applying iterative best responses with the learned models. A key structural identity links virtual valuation curvature $\\phi_i'(u)\\ge c_i$ to $s$-concavity with $s_i=c_i-1$, enabling a tuning-free estimator and equilibrium analysis through a contraction of the best-response map.\n\nIn this paper, the authors prove (1) The existence of a unique Nash Equilibrium, characterized by $p_i^\\star=\\Pi_{P_i}, g_i(\\langle \\gamma_i,p_{-i}^\\star\\rangle)/\\beta_i$ where $g_i(u)=u-\\phi_i^{-1}(u)$, and the joint best-response operator $\\Gamma$ is a contraction when $\\sup_i |g_i'|_\\infty |\\gamma_i|_1/\\beta_i<1$. (2) The concentration for parameters: $|\\hat\\theta_i-\\theta_i|_2=O\\big(\\sqrt{(N\\log n^{(1)}i)/n^{(1)}i}\\big)$; sup-norm nonparametric error $\\mathbb{E}\\big[\\sup{u\\in K}|\\hat\\psi{i,\\hat\\theta_i}(u)-\\psi_i(u)|\\big]=O\\big((\\log n^{(2)}_i/n^{(2)}_i)^{2/5}\\big)$. And (3) the regret rate $O\\big(T^\\xi+T^{1-2\\xi/5} N^{3/2} (\\log T)^{2/5}\\big)$ and $\\mathbb{E}|p^{(T)}-p^\\star|_2^2=O\\big(N^{3/2} T^{-2\\xi/5}(\\log T)^{2/5}\\big)$, optimized at $\\xi=5/7$ to yield $\\tilde O(N^{3/2}T^{5/7})$ regret and $\\tilde O(N^{3/4}T^{-1/7})$ equilibrium convergence.\n\nThe authors also conduct numerical experiments with $N=2,4,6$ and log-concave links show convergence to NE and sublinear regret aligned with the theoretical rates, and finally a robustness check. Compared to existing literature, this work generalizes linear-demand competition with $\\tilde O(\\sqrt{T})$ regret to semiparametric monotone SIM under shape constraints and matches the known $\\tilde O(T^{5/7})$ rate in the monopolistic SIM case while introducing a tuning-free $s$-concave NPLS analysis and a new equivalence between $\\phi_i'$ and $s$-concavity.", "questions": "(1) How should practitioners set $c_i$ (and $s_i=c_i-1$) if unknown? Is there a safe adaptive surrogate (under/overestimation) that preserves contraction and regret rates?\n\n(2) Do you conjecture a minimax lower bound matching $T^{5/7}$ for monotone $s$-concave SIM in this feedback model? Where is the main slack otherwise?\n\n(3) Please elaborate on the exploration distribution assumption (elliptical with $g(x+y)=g(x)g(y)$). Also, if exploration uses truncated Gaussians within $P$ (non-elliptical full support), how do concentration results and the decoupling arguments change?\n\nSome typos to notice:\nLine 239, “coponents”", "limitations": "", "rating": 4, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "(1) Technical connection between $\\phi_i'(u)\\ge c_i$ and $s$-concavity ($s_i=c_i-1$), enabling both equilibrium characterization and estimation under shape constraints.\n\n(2) Sup-norm concentration for $h\\circ$concave regression with $O((\\log n/n)^{2/5})$ rates; careful two-stage estimation to decouple dependencies.\n\n(3) Broadens beyond linear or fixed parametric nonlinear demand; theory covers NE existence/uniqueness and convergence under strategic coupling.\n\n(4) Clean regret/convergence bounds tied to estimation rates; simulations align with theory.\n\nOverall, this is a good work.", "weaknesses": "There are some issues that I’m most concerned about:\n\n(1) The assumed knowledge on $c_i$ or $s_i$, which is a very strong assumption.\n\n(2) The optimality of $\\tilde O(N^{3/2}T^{5/7})$ regret. A matching lower bound is not established.\n\n(3) The condition of contraction $\\sup_i |g_i'|_\\infty |\\gamma_i|_1/\\beta_i<1$ is not well justified in real-world markets.", "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)