Dynamic Assortment Selection and Pricing with Censored Preference Feedback
Authors: Jung-hun Kim
Min-hwan Oh
Venue: ICLR 2025 Poster (2025)
Keywords: Dynamic Pricing
Preference Feedback
Bandits
Primary area: learning theory
TL;DR: In this study, we investigate the problem of dynamic multi-product selection and pricing by introducing a novel framework based on a censored multinomial logit (C-MNL) choice model.

Abstract: In this study, we investigate the problem of dynamic multi-product selection and pricing by introducing a novel framework based on a *censored multinomial logit* (C-MNL) choice model. In this model, sellers present a set of products with prices, and buyers filter out products priced above their valuation, purchasing at most one product from the remaining options based on their preferences. The goal is to maximize seller revenue by dynamically adjusting product offerings and prices, while learning both product valuations and buyer preferences through purchase feedback. To achieve this, we propose a Lower Confidence Bound (LCB) pricing strategy. By combining this pricing strategy with either an Upper Confidence Bound (UCB) or Thompson Sampling (TS) product selection approach, our algorithms achieve regret bounds of $\tilde{O}(d^{\frac{3}{2}}\sqrt{T/\kappa})$ and $\tilde{O}(d^{2}\sqrt{T/\kappa})$, respectively. Finally, we demonstrate the performance of our methods through simulations.

Published as a conference paper at ICLR 2025
DYNAMIC ASSORTMENT SELECTION AND PRICING WITH CENSORED PREFERENCE FEEDBACK
Jung-hun Kim
Min-hwan Oh
Seoul National University junghunkim@snu. ac.kr
Seoul National University minoh@snu.cm kc.kr
ABSTRACT
In this study, we investigate the problem of dynamic multi-produre selection and pricing by introducing novel framework based on censored multinomial logit (C-MNL) choice model. In this model, sellers present a set of products with prices, and buyers filter out products priced above their valuation, purchasing most one product from the remaining options based on their preferences. The goal is maximize seller revenue by dynamically adjusting product offerings and prices, while learning both product valuations and buyer preferences through pur- chase feedback. To achieve this, we propose a Lower Confidence Bound (LCB) pricing strategy. By combining this pricing strategy with either an Upper Confi- dence Bound (UCB) or Thompson Sampling (TS) product selection approach, our algorithms achieve regret bounds Ō ( kK) and (d /T/R). respectively. Finally, demonstrate the performance of our methods through simulations.
INTRODUCTION
The rapid growth of online markets has underscored the critical importance of developing strategies for dynamic pricing to maximize revenue. In these markets, sellers have the flexibility to adjust the prices of products sequentially in response to buyer behavior. However, optimizing prices is not trivial task. To effectively set prices, sellers must learn the underlying demand parameters, as buyers make purchasing decisions based on their preferences and willingness to pay, modeled by demand functions (Bertsimas Perakis 2006
Cheung et al., 2017 den Boer Zwart 2015 Javanmard & Nazerzadeh| [019 Cohen et al. 2020 Javanmard & Nazerzadeh| 2019 Luo et al. 2022 Fan al.
2024 Shah et al., 2019 Xu & Wang 2021 Choi et al. (023). While the prior work has focused on
dynamically adjusting prices for single products, real-world applications such e-commerce, hotel reservations, and air travel often involve multiple products, further complicating the pricing strategy
(Den Boer 2014 Ferreira et al. 2018 Javanmard al. 2020 Goyal & Perivier 2021).
In practice, sellers must do more than just set thices-they also need to determine which products to offer. Buyers purcahse product based on their preferences for available items, and this purchasing process is influenced by the price. Higher prices reduce the likelihood of a purchase, as buyers filter out products priced above their perceived value. This dynamic interplay between pricing and buyer preferences is a fundamental aspect of real-world online markets, making it essential to model both product selection and pricing together.
In this work, we tackle the problem of dynamic multi- product pricing and selection by developing a novel framework that captures the censored behavior of buyers-wher where buyers consider only those products priced below their valuation and purchase one product from the remaining options. To model this behavior, we extend the widely used multinomial logit (MNL. choice model (Agrawal al. 2017a b. Oh & Iyengar 2021 2019) censored MNL (C-MNL) model. This model al- lows us to capture buyer behavior more accurately in scenarios where product prices impact buyer choices. In our framework, sellers dynamically lear both the product valuations and buyer prefer- ences, all while facing the challenge of not receiving feedback on which products buyers filtered out due to high prices, reflecting real-world conditions.
To address the inherent uncertainty in buyer behavior, we propose a novel Lower Confidence Bound (L.B) pricing strategy, which sets lower initial prices to encourage exploration and avoid price

---

Published as a conference paper at ICLR 2025
censorship. In combination with Upper Confidence Bound (UCB) Thompson Sampling (TS) strategies for product assortment selection, we provide algorithms that not only maximize revenue but also efficiently balance exploration and exploitation in the face of censored feedback. Through theoretical analysis, we derive regret bounds for our algorithms, and we validate their performance using synthetic datasets.
Summary of Our Contributions.
We propose novel framework for dynamic multi-produe selection and pricing that in- corporates censored version of the multinomial logit (C-MNL) model. In this model, buyers filter out overpriced products and choose from the remaining options based on their preferences.
We introduce Lower Confidence Bound (LCB)-based pricing strategy promote explo- ration by setting lower prices, avoiding buyer censorship, and facilitating the learning of buyer preferences and product valuations.
We develop two algorithms that combine LCB pricing with Upper Confidence Bound (UCB) and Thompson Sampling (TS) for assortment selection, achieving regret bounds of Odd /K) and O(d /K),,, respectively.
We provide extensive theoretical analysis, including regret bounds, and validate the effec- tiveness of our algorithms using synthetic datasets, demonstrating their superiority over existing approaches.
2 RELATED WORK
Dynamic Pricing and Learning Dynamic pricing with learning demand functions or market val-
has been widely studied (Bertsimas & Perakis 2006 Cheung al. 2017 den Boer & ZZwart
2015
Javanmard & Nazerzadeh] 2019] Cohen et al. 2020 Luo et al. [002]]Xu Xu & Wang [021 Fan
al.
2024
Shah al. [019 Choi et al. [023] Den Boer 2014: Ferreira et al. al.] 2018 Javanmard
iet al.
2020 Goyal & Perivier 2021). However, previous work typically assumes that products are
introduced arbitrarily or stochastically, meaning the products themselves are given rather than be- ing part of the decision-makinn process. In contrast, our study incorporates preference model for dynamic selection and pricing, where the agent must determine the assortment of products to offer with prices.
We note that Javanmard et al. 2020); Goyal & Perivier (2021 : Erginbas al. (2023) considered MNL structure for dynamic pricing, which was widely considered in the assortment bandits lit- crature (Agrawal et al. 70 by Oh & Iyengar, 2021 2019). Based on the MNL structure, the previous pricing strategies have focused solely optimizing revenue function. Notably, Davanmard et al. 22200;; Perivier & Goyal (2022) examined scenarios where the assortment is predetermined rather than chosen by the agent under the dynamic pricing problems, and Erginbas al. (2023) di- rectly extended Goyal & Perivier (202T) by considering assortment selection under the same MNL structure. Moreover, Javanmard al. (2020) consider i.i.d feature vectors fixed over time.
In our study, we utilize the MNL model with arbitrary features at each time to capture buyer pref- erences. Inspired by real-world scenarios, we further incorporate activation functions to address the non-continuous nature of buyer behavior, specifically their acceptable price thresholds. The pres- ence of activation functions in our MNL model prevents a direct conversion the standard MNL structure, distinguishing our work from that of Javanmard et al. (2020); Goyal & Perivier (202)); Erginbas et al. (003).. Furthermore, we address multi munti-product setting where the agent not only prices but also selects products at each time. As a result, we must develop novel strategy for both pricing and assortment selection to address this challenge.
Notably, while activation functions for buyer demand have been considered in Javanmard & Naz- erzadeh (2019); Cohen et al. (2020); [uo et al. (2022); Xu & Wang (202T): Fan al. (2024); Shah al. (2019); Choi et al. (2023). these studies focused on single-product offered by the environment with single binary feedback at each time indicating whether the product was purchased or not. In contrast, examine a multi-produs setting where the agent must both select and price multiple products while receiving preference feedback, a scenario commonly observed in real-world online markets.
2

---

Published as a conference paper at ICLR 2025
Arms
Arms
Arms
St
St
St
2
P2.r
P2.t S V2,t
3
Arm
P4,t
P4.t V4,6
purchased by the user.
Ps, Vs,
with prices Pir for St offered the user.
Arm 5 is censored by the user.
(a) The agent offer an assort- ment of arms S. with price Pu, for i St.
(b) Arms E St satisfying
(c) The user purchases an arm from the remaining arms in St based on preference.
> Us,t are censored by the
user.
Figure 1: The illustration describes the process involved in making purchase.
PROBLEM STATEMENT
There are N arms (products) in the market. As illustrated in Figure 1 at each time t [T]. (a) an agent (seller) selects a set of arms S, S [ referred to "assortment," to a user (buyer) with a size constraint [S|| < K(S N). At the same time, the agent prices each arm i E S, as Pi, E I2 and suggests the assortment with the corresponding prices to the user. (b) Then, based on the valuation Vi, and price Ps,t for each arm S₁, the user filters out any arms E S, where the price exceeds their valuation, i.c., V1 Pi, (c) Finally, the purchases at most arm from the remaining options based on preference. In what follows, we describe our models for the user behavior and the revenue of the agent in more detail.
There are latent parameters 0g and fa E Rdd (unknown to the agent) for valuation and price sensitiv- ity, respectively. At each time I, each arm i [N] has known feature information Ji,r and Wi,t Rd for its valuation and price sensitivity, respectively. Then the (latent) valuation of each arm for the user defined U, 0, 2 O. We also consider that there (latent) price sensitivity parame-
ters as O;,t == w. ax 2 0. In this work, we propose modification of the conventional MNL choice model with threshold-bs based activation functions, which name the censored multinomial logit (C-MNL) choice model.
Definition (Censored multinomial logit choice model) Let set of prices Pt (pea)iss Then, given St and Pt. the user purchases an arm E S₁ by paying pi, according to the probability defined as follows:
exp(ei. - aa......)... v.,))
(il = 1 Ejes, exp(0;, a.) S vza))
(I)
From the activation function in the above definition, the user considers purchasing only the arms i S, satisfying that its price is lower than the user's valuation (or willingness to pay) as Pi, S U;,-- We also note that higher price for an arm decreases the user's preference for it, while higher valuation indicates stronger preference. For notation simplicity, we use f" := [0.; 0a] E I22d and
<p((p) = [τ., -p E id Then the C-MNL of ( can be represented as
exp(xI,,0, (.P. (T,,,) P.(i(S.,p)) = 1+ Ejes, exp(x 0r (.P.01 1 S xT,00) exp(2..(Pa.) T0 S sTT,0o)
1 Ejes, exp exp(zz,((5,))) 0²) ( $ 0.)
As in the previous literature for MNL, it is allowed for each user to choose an outside option (ia), or not to choose any, as IP, (1o Pt) 1+E,es, exp(2,,((E.)) 10)) ". Importantly, each
3

---

Published as a conference paper at ICLR 2025
time t, the agent only observes feedback of chosen arm i, (at most one) but does not observe feed- back on which arms are censored from the activation function based on the latent user's 's valuation. This makes it challenging learn the valuation from the preference feedback, and the naive pricing strategies for maximizing revenue (Javanmand et al. 2020 Goyal & Perivier 2021 Erginbas et al, 2023) do not work properly for model.
The expected revenue from chosen arm E S, is represented as (S,)(S)) = P., (i p.). Then the overall expected revenue for the agent is formulated as
Pi, exp(2x.(P.)) 87)1(pp S xl. Ejes, (xp(2))(()ja) (Pj, S 0,)
(st,
Σ (S.) VES.
E iES.
For notation simplicity, p = (Di) Then we define oracle policy (with prior knowl- edge of (²)) regarding assortment and prices such that
p?) E
arg max SC[M] 2o-18 SK.
Rs
Then given St and p. for all from a policy a, regret is defined as
R (T) = Σ
E[R,(S; pi) pt).
EE(T]
The goal of this problem is to find a policy т that minimizes regret.
ALGORITHMM AND REGRET ANALYSES
4.1 UCB-BASED ASSORTMENT-SELECTT WITH LCB PRICING: UCBA-LCBP
Here we propose UCB-based assortment-selectio with LCB pricing algorithm (Algorithm D as (p.) (p.))a To)
follows. We denote by (t,((i)S.p) = I+Σ,es (xp(a,,(;;))) the choice probability without the activation functions. Let the negative log-likelihood (0) == - Eies, Yt, log Pt. Pt) where U/ E {0, } is observed preference feedback (1 denotes a choice, and otherwise) and define the gradient of the likelihood as
ge Vofe(0) Σ (P.o((()). (P(.))
SES.
We also define gram matrices from (2)( as follows:
(0) = Σ
- R.G(5....PP.0.::sw..............
Sr
ijes,
(o) = Σ
Σ $.ES.
Pt
(3)
iES.
Then we construct the estimator of 0. E 2d2d for 0* from the online mirror descent with (2) and as studied by Zhang & Sugiyama (024): ) Lee Oh (2024). within the range of θ (
||01d/||2 S and [ S 1j. which is described in Line
Now we explain the details regarding the strategy for the decision of price and assortment. For the price strategy, we construct the lower confidence bound (LCB) of the valuation of arms. Let where 7 is the number of estimator updates for price, H; Al2 + E (o,), and Ho,: AIa E'=1 (o,)(0s) for some constant C1 > 0 and X 0. We use grom for representing vector consisting of elements from index n to in R22 Then denote the estimator regarding valuation by 0u, := 0.:'d Let f, be the time step when 7-th update of the estimation for price occurs and we use (,,(r) := 0e,t, for the pricing strategy. Then with a constant C' for the time steps corresponding to the 7-th update, we construct the lower confidence bound (LCB) of the valuation of arm E [N] as
3, = C1 di log
U == 2. 1C
4

---

Published as a conference paper at ICLR 2025
Algorithm UCBBB Assortmment-selectionn with LCB Pricing (UCBA-LCBP)
Input: 7, Br,
Init: 4 1,4, f- 1, (1()) f 0.
for f l...., do
He - N2zd + - Gz(O.) + G with 3
He Alad Σ 2 (o,),) with 3
Ho. + Ma + Ex=1 G (0,) with
arg sigeegee 91-1 10 1 1 2n 110 0.-111 11
with 2
Estimation
if det(H)) > dett (d,)(H,.)) then + +
(r,(T)) + Be,er(= (110))
for [N] do
10
Ei, - (..00rrr) VC 10
D LCB for valuation
11
Pi, + v.
Price selection w/ LCB
12
01,t - x 21.00tt + Br 33
D UCB for valuation UCB for utility
The t (Pi.t) 0. + (-llza,(PEa)) 1 2
14
S. argg Eies 1+2 exp(T,,)))
The exp((.e)
Assortment selection w/ UCB
15
Offer S, with prices p: = {Pit)iss
16
Observe preference (purchase) feedback Vi.t (0, 1) for S.
We use notation x+ max(x, 0} for R. Then, for the LCB pricing strategy, we set the price of arm using its LCB
Pi.
Importantly, from this pricing strategy, the algorithm can effectively explore arms avoiding censor- ship because the arm having a small price is likely to be activated from the user's threshold in the C-MNL choice model. In the analysis, under the condition of favorable event regarding the LCB,
we can appropriately handle the preference feedback from C-MNL for estimating 0 with 0, How- the conditional analysis for estimation introduces regret with each update. To solve this issue. periodically update the estimator 0u.(7) for LCB with constant C as described in Line 6 without hurting regret (in order) from estimation error.
Next, for the assortment selection, we construct upper confidence bounds (UCB) for valuation U and preference utility ui, as U, and T. respectively. We construct UCB for the valuation as
Uyt == 0.. + 3r 11
Interestingly, when constructing Ui, regarding utility us,e = (pt,)) TØ 9h, it is required to consider enhanced silanced-expllraation under the uncertainty regarding both 0 and ps, (in 21,((P..)) We construct
Th := (p..) TO, 3,112,, +2VC3,
where Br (P1l,,,(Pr..)) n comes from uncertainty of 0, and 2/C3, | comes from that of Ps, in (pr.)) Then, using the UCB indexes, the assortment is chosen from
T exp exp(TT.))
S E arg max Σ
1 1 Σ jeS exp(
SCINHSSK
We 7) log(K 1) and À max(8Adn, 192v2n) for the algorithm.
5

---

Tachieves regret bound of Published as a conference paper at ICLR 2025
4.2 REGRET ANALYSIS OF ALGORITHM| 1
(UCBA-LCBP)
Similar to previous work for logistic and MNL bandit (Oh & Iyengar 2019 2021 Lee & Oh 2024
Goyal Perivier 2021| Erginbas et al. 2023 Faury [ Abeille et al. (021). we consider
the following regularity condition and definition for regret analysis.
Assumption |10.12 - L, 10all2 - 1, ||a,elle S 1, and ||w,,ll2 & 1 for all i e [M], te [T]
(0 2d | ||2 I 1 and |00+1:2d12 I 1}. Then define problem-dependent quantity regarding non-linearlity of the MNL structure as follows.
Recall θ
K relT1,,e0,eSS[MMueei... Pro((iS..)PP,o00055..
inf
We note that the worst-case, 1/N = O(K²) from the definition of Pt,((-S.pp) with Assumption
Then A achieves the regret bound in the following.
Theorem Under Assumption
the policy of Algorithm 7
(T) = d T/R
Proof The full version of the proof is provided in Appendix A.2 Here we provide a proof sketch.
We first define event E, {1|Ø_ - 0"1 S 3r. Vs S { and Ey holds with high probability. In what follows, we assume that E, holds each time
T Then For notation simplicity, we use Vi, == 2T,,00m Or. Ui == (15,) To and uh, =xp()))) 0"
can show that for all E [N] and E [7]. we have
1 S 0,e S U. and une S Th
(4)
For the regret analysis, we need to obtain a bound for Re(S; - PS)
pl exp(ux.) (pt, I v1 E+E exp(u,,) S vz,e)
Pi. exp(ux,,) S via))
Σ SES;
Σ iES.
(5)
1+ Σ Ejes, (xp(u,,)) A(pj, S vz,e)*
(,,( T + 23,,, (P. + 1/ so that Uz S Th,-- For the first term in 5 with and the UCB-based as- sortment selection policy, we can show that
For the purpose of analysis, we define Thd
Ph, exp(ux,)) (PT, v.,) 1+ Eje;e jes exp(u,,) (p)) I vj,a)
S EiES, Ui exp(T(,))
(6)
I+E (xp(T(,))
ES
For the second term in 5 with and the LCB-based pricing, we have
Pi. exp(ue,, S v. Eies, wtt exp(1;,) + Ees, ( ( $ vnee) 1 Eies, exp(u",)
Σ
From 5 16). and
we have
Eies, Una exp(u(1))
Eies, ut, exp(uf,)
R,(S Re(Se, p.)
<
It Eies, (p(
It Eies, exp(uf)) Eies, ett exp(T(,.)
Eies, The (xp((T(.)) Eies, et. (T.(T)))
Eies, tit exp(u(,) 1+ Eies, exp(u),)
+
1+ Eies, exp(T!,,) 1 Eies, exp(T!,)
Eies, exp(T(,,)

---

Published as a conference paper at ICLR 2025
Let Ti be the value of T at the time step t. We can show that E[3,,] = (d) and B[S = Ö(P)).
Then, for a bound of the first two terms in (8) with expectation bounds for Prr and 8 in the above and elliptical potential bounds, we show that
ies U.e (T.) + Eies. exp(T.,.)
Eies, ui, exp(Ti,.)
((E))
- Eies. (xp(Ti..))
1E[2]
=
Σ (E(TT
E
(
3r, max iES,
| m. :. I(E:))
= = d (TVVT
(9)
Likewise, for the bound of the last two terms in 8 show that
Eies, Dif exp(une) Σ E [Fr (E[T]
Eies, 2he exp(uf,)) 1+ Eies, exp(u
I(E.) = -
d
(10)
I Eies, exp(ur,))
which conclude the proof with (8. (9) and the fact that Ey holds with a high probability.
Under the C-MNL model, our algorithm can achieve the tight regret bound with respect to T as those established in standard MNL bandits (Oh & Iyengar 2021 and dynamic pricing under MNL with arbitrary features (Goyal & Perivier 2021: Erginbas al. 2023). The regret bounds of Goyal & Perivier (2021]: y Erginbas et al. (2023) for the MNL dynamic pricing problems include 1 1/K / in the leading term where, in their work, was assumed be constant term. In the worst case where 1/K = O(K), their regret bounds become Ö(K Our regret bound contains only /1/K in the leading term, allowing it to remain O(K (T) for large enough T' in the worst case. Moreover, the previous works (Goyal Perivier 2021 Erginbas et al. 2023 assumed that v._ 2 with positive constant L> and their regret bounds include 1/L" for n 2 1. This leads trivial regret bounds in the worst case when I. is small, whereas our regret bound does not depend on L. Regarding the dimensionality, the analysis of our new censored MNL model is significantly more challenging and involved due to the presence of activation functions, which adds complexity. As result, our regret bound scales with d'a However, whether this dependency can be improved remains an open question.
We now discuss the algorithmic differences between method and the proposed in Goyal & Perivier (202T): Erginbas et al. (2023). In the prior work of Goyal & Perivier (2021): Erginbas et al. (2023), the price is determined by maximizing revenue each time. However, in our C-MNL framework, we cannot estimate 8" using the revenue-mane maximizingiii price due to the hidden nature of non-purchased feedback regarding whether it is due to stochastic preference or elimination by an activation function. To address this issue, we employ an LCB pricing strategy that enhances exploration across all arms by adhering acceptable user prices. Since our pessimistic pricing strategy introduces a gap from the optimal price, we further incorporate an exploration-enhanee strategy for choosing assortments.
Additionally, our algorithm is computationally more efficient since it does not require solving an optimization problem for pricing decisions, which was necessary in the previous work. We also note that regarding the computational costs of assortment selection, which is common in all MNL bandit literature, the assortment optimization can be computed by solving an LP (Davis et al. 2013).
4.3 TS-BASED ASSORTMENT-SELECTIO WITH LCB PRICING: TSA-LCBP
Here we propose Thompson sampling -bS)-based assortmment-selection with LCB pricing algo- rithm (Algorithm 2 As in Algorithm
we first estimate 0, using the online mirror descent within the range of θ {0 E 2d || < 1 and ||@++122d| < 1}. For determining price, we utilize the LCB pricing as Pa, = 2it where, recall, Eit 0.,,0,,(7) Br [+1l:,, with
3, = C C log(T) log(K).
For choosing the assortment, sample two different types of instances from Gaussian distributions; one is for valuation and the other is for preference utility, each of which is sampled for M times as
gim) R and 0(:) Id2d for E [M], respectively. We set M- [1
Tog(1 1o/v/_/ 7. Then we
1og(2N)
7

---

Published as a conference paper at ICLR 2025
Algorithm 2 TS-based Assortmeent-selection with LCB Pricing (TSA-LCBP)
Input: 7, M, B,, C>1
Init: 7 4 1,4, f- 1, uu(1) f- 0a
for 1 l...., do
H₂ t Xlzd + Σ Gz(O.) + GG with 3
H4 - A22d Σ _=1 (0,) with
Ha,1 + Ala + E.=1 G. (0.) with
0, mingee Dr (0, 0 + 27p 10 O p.-- with 2
D Estimation
Sample (0ure) IMEMM independently from (00,,
Sample (0(mh ImE(M independently from (/ 2 "
if det H4) > C Cede( (H,,) then
T +1 +
(r)(r) t (= 01,00)
for iE [N] do
Ei t T (u(r)) VOB-IIai,lleE
D LCB for valuation
Pi, f _
Price selection w/ LCB TS for valuation
The f arg maxme|M Zi, O
The < Di.t De,
U4e f arg maxme(MM Z1,8 (pr,e) TO + 807
> TS for utility Assortment selection w/ TS
S: E arg Sag Eies T+ exp(a)a))
T. explū..)
Offer St with prices p: = {pi,t
Observe preference (purchase) feedback yi. (0, 13 for S.
construct TS indexes regarding the valuation and utility as
1iet = arg max x,,,00 and Ugee = arg max 25, (pt,)) m(()) + 167,, respectively, me(M]
M
where 7,, U,.t TT,,OO.t. For the utility of ues. have consider the uncertainty regarding Pi, as well as 0r, which leads to requiring an additional exploration term Mh. Then the assortment is determined from
U exp (ūr.)) 1+ jES exp(ū)e)
S. E arg max SCINHISSK
Σ T+
In the following, we provide a regret bound of the algorithm by setting n 1/2 loog( + 1) + 3 and max(84dm, 192v2n).
4.4 REGRET ANALYSIS OF ALGORITHM (TSA-LCBP)
Theorem Under Assumption 1 the policy π of Algorithm 2 acchiees a regret bound of
RT Ō da
Proof The full version of the proof is provided in Appendix A.3 Here we provide some key components of the proof. We first define event E, = -1100 000
1000--0-11 || S Bc, Vs S t} and Eg holds with high probability. Let A; (i S Př,, S v/,} and, recall, V/,t 0,,00, d4,s 21,(pt;,) TØ", and uh, 21, (P.,)) T Then under F,, from the pricing and assortment selection strategies, we can show that
(S .(S)..P) R.(SS. pi) < Σier: Ui exp(uit)
Eies, eit exp(u,,) I+Eiss exp(u?,)
(11)
1+ Eier exp(ux.)
8

---

Published as a conference paper at ICLR 2025
We define event O such that for all [N], we have
[ x 2T,,ou,ll S 7 || n.t and بūف - (pt,)) T0,l 80'r (C
which is shown to hold with high probability. We also define event E(!)) such that for all i E [N] we have Di,t 2 Vi,e and U, 2 we,s, which shown to holds least a positive constant. Let
E. E, n E Then we can show that P(E Eb) 2 1/8veT where Fi-1 is the filtration containing information before t.
Let ã., Zi,r (pE.)) - Ea-Pa., (.IS....) (=,,) and ã.,, Fi,t Bymp, (-1S. (oi and 7 Br, / //ddogg(MM (MI) where 7u is the value of time 6. For the ease of presentation, we use
L = (max (2,,
+ max
el (nm.) (x + + (max VESt
|| + max [i,ee|
xESt
eES
rES,
+ 71 E P. (ilS., (() (I + V S.
Σ
|
RES.
With constant lower bound for PEE Ex) and elliptical potential bounds, by omitting some details, we can show that
EiEA; Uhe exp(ut,)
Eies, ett exp(u;,)) ((E)) FF-1
E
+ DiEA exp(u:;)
1 Eies, expluf,))
o
(E
B L F.-1,E, E. P(B)FL))) - (
which concludes the proof with 11 and the fact that Ey holds with a high probability.
To the best of our knowledge, this is the first work to apply Thompson Sampling (TS) to dynamic pricing under MNL functions, whereas the previous related works focused on UCB method (Ergin- bas et al. 2023) (or did not consider assortment selection (Goyal & Perivier 2021)). Additionally, prior work on TS for MNL bandits (Oh & Iyengar 2019) includes 1/k in the regret bound that
(((/k)VTT) and requires computationally intensive estimation with an Ott) cost at each time step t. In contrast, by using online mirror descent updates, our TS algorithm reduces the k dependency in the main term of the regret bound with Ö(vT/K) for large enough T and provides computationally efficient online updates with an ((1) cost for estimation in MNL bandits. It is also worth noting that our TS regret bound has an additional v term compared to the UCB algorithm (Algorithm This phenomenon of increased regret with respect d. compared to that of UCB, is consistent with observations from previous TS- bandit literature (Oh & Iyengar 2019 Agrawal & Goyal
2013 Abeille & Lazaric 2017). Furthermore, achieving regret bound for TS, even after UCB, is
widely considered an established contribution in bandit literature (Agrawal & Goyal 2013
Abeille
Lazaric 2017
Kim & Oh 2024).
EXPERIMENTS
Here, present numerical results using synthetic datasets with varying numbers of products N For the experiments, we generate each element in 0, and 02 from the uniform distribution (0. 1) and normalize them. We also generate features in the same way. We set K Unfortunately, there is no algorithm that can be directly applied to our novel setting. Therefore, for the benchmarks, we utilize previous algorithms proposed for dynamic pricing under MNL model such as DASP-MNL proposed in Erginbas et al.] (023) and ONM (online newton method) in Goyal & Perivier (202T). We note that ONM works under a given assortment rather than selecting one, so we adjust the method by adopting the method for the assortment optimization in Erginbas et al. 2023). We also utilize the method of Explore-then-commic (ETC) (Lattimore & Szepesvári (020) as benchmark, which conducts exploration over the first 2/3 time steps and then exploits for the remainder of the time. In Figure 2, we can observe other benchmarks do not work properly in our setting and our algorithms outperform the benchmarks with sublinear regret.
and d = 4.
Source code:

---

Published as a conference paper at ICLR 2025
ONM
DASP-MNL
ETC
UCBA-LCBP (Algonthm 11
TSA-LCBP (Algorithm 2)
1e4
N-
1e4
N5
1e4
N 20
2-
24
2
1
1
1
0
0
2
3
4
5
2
3
4
2
3
Time
1e4
Time step
le4
Time stop
le4
Figure 2: Experimental results for the regret of algorithms
RANDOMNESS IN ACTIVATION FUNCTION.
We further investigate the presence of randomness in the activation function in C-MNL. Let Si,e be a zero-mean random noise drawn from the range of [-c, c] for some 0 < S 1. we consider
exp(=i,((i..) 0 (pr. S (2T, + (.,)+ (il... 1+ Ejes, (xp(2),((p,.)) 0*) (p) I (x), 0g + (1,)))
We propose variant of Algorithm [ (Algorithm 3 in Appendix A.4) using robust LCB pricing strategy, which achieves Ö(d /T/x) when OLIvVT). Further details on the algorithm and theorem can be found in Appendix A.4
7 CONCLUSION
In this study, explore dynamic multi multi-products selection and pricing within new framework of the censored multi-nomial logit choice model. We introduce algorithms that incorporate an LCB pricing strategy along with either UCB TS product selection strategy. These algorithms achieve regret bounds of ( TTKk) and Ōdd /T/m),, respectively. Lastly, we validate our algorithms through experiments with synthetic datasets.
Reproducibility Statement. Complete proofs the theorems are included in the appendix.
8 ACKNOWLEDGMENTS
The authors thank Joongkyu Lee for providing useful code. This work was supported by the Global- LAMP Program the National Research Foundation Korea (NRF) grant funded by the Ministry of Education (No. RS-2023-00301970 and also supported by the Korea government (MSIT) (No. RS RS-2022-NR071S8 853 and RS- 003-0223300 and Al-Bio Research Grant through Seoul National University.
REFERENCES
Yasin Abbasi- Yadkor,, Dávid Pál, and Csaba Szepesvári. Improved algorithms for linear stochastic bandits. Advances in neural information processing systems, 24, 2011.
Mare Abeille and Alessandro Lazaric. Linear thompson sampling revisited. In Artificial Intelligence and Statistics, pp. 176-184, PMLR, 2017.
Mare Abeille, Louis Faury, and Clément Calauzènes. Instance-wise minimax-optimal algorithms for logistic bandits. In International Conference on Artificial Intelligence and Statistics, pp. 3691- 3699. PMLR. 2021.
Shipra Agrawal and Navin Goyal. Thompson sampling for contextual bandits with linear payoffs. In International conference machine learning, pp. 127-135. PMLR, 2013.
10

---

Published as a conference paper at ICLR 2025
Shipra Agrawal, Vashist Avadhanula, Vineet Goyal, and Assaf Zeevi Mnl-bandit: A dynamic learning approach to assortment selection. arXiv preprint 17X6v:1706.03880. 2017a.
Shipra Agrawal, Vashist Avadhanula, Vineet Goyal, and Assaf Zeevi. Thompson sampling for the mnl-bandit. In Conference on learning theory, pp. 76-78. PMLR, 2017b.
Dimitris Bertsimas and Georgia Perakis. Dynamic pricing: A learning approach. Mathematical and computational models for congestion charging, pp. 45-79, 2006.
Wang Chi Cheung, David Simchi-Levi, and He Wang. Dynamic pricing and demand learning with limited price experimentation. Operations Research, 65(6):122--131, 2017.
Young-Geun Choi, Gi-Soo Kim, Choi Yunseo, Wooseong Cho, Myunghee Cho Paik, and Min-hwan Oh. Semi-parametric contextual pricing algorithm using cox proportional hazards model. In International Conference on Machine Learning, pp. 5771-5786. PMLR, 2023.
Maxime C Cohen, Ilan Lobel, and Renato Paes Leme. Feature- based dynamic pricing. Management Science, 66(1 (:9(1)):4911141 4943, 2020.
James Davis, Guillermo Gallego, and Huseyin Topaloglu. Assortment planning under the multino- mial logit model with totally unimodular constraint structures. Work in Progress, 2013.
Arnoud V Den Boer. Dynamic pricing with multiple products and partially specified demand distri- bution. Mathematics of operations research, 39-8)886--888 2014.
Arnoud V den Boer and Bert Zwart. Dynamic pricing and learning with finite inventories. Opera- lions research, 63(4))965 978, 2015.
Yigit Efe Erginbas, Kannan Ramchandran, and Thomas Courtade. Dynamic assortment selection and pricing with learning. Openreview, 2023.
Jianqing Fan, Yongyi Guo, and Mengxin Yu. Policy optimization using semiparametric models for dynamic pricing. Journal of the American Statistical Association, 1196545):552-664 2024.
Louis Faury, Mare Abeille, Clément Calauzènes, and Olivier Fercoq. Improved optimistic algo- rithms for logistic bandits. In International Conference on Machine Learning, pp. 3052-3060.
PMLR, 2020.
Kris Johnson Ferreira, David Simchi-Levi. and He Wang. Online network revenue management using thompson sampling. Operations research, 66(6):1586-166 2018.
Vineet Goyal and Noemie Perivier. Dynamic pricing and assortment under contextual mnl demand. arXiv preprint arXiv:21 10.10888 2021.
Adel Javanmard and Hamid Nazerzadeh. Dynamic pricing in high-dimensions. Journal of Machine Learning Research, 20(9):1-49, 2019..
Adel Javanmard, Hamid Nazerzadeh, and Simeng Shao. Multi-prode Multi-product dynamic pricing in high- dimensions with heterogeneous price sensitivity. In 2020 IEEE International Symposium on In- formation Theory (ISIT), pp. 2652-2651 2657. IEEE, 2020.
Jung-hun Kim and Min-hwan Oh. Queueing matching bandits with preference feedback. arXiv preprint 1.XXi:2410011099 2024.
Tor Lattimore and Csaba Szepesvári. Bandit algorithms. Cambridge University Press, 2020.
Joongkyu Lee and Min-hwan Oh. Nearly minimax optimal regret for multinomial logistic bandit. Advances in Neural Information Processing Systems, 37:109003-109065 2024.
Yiyun Luo, Will Wei Sun, and Yufeng Liu. Contextual dynamic pricing with unknown noise: Explore-then-ude strategy and improved regrets. Advances in Neural Information Processing Systems, 35:37445-37457, 2022.
Min-hwan Oh and Garud Iyengar. Thompson sampling for multinomial logit contextual bandits. Advances in Neural Information Processing Systems, 32, 2019.
11

---

Published as a conference paper at ICLR 2025
Min-hwan Oh and Garud Iyengar. Multinomial logit contextual bandits: Provable optimality and practicality. Proceedings of the AAAI conference on artificial intelligence, volume 35, pp- 9205-9213, 2021.
Noemie Perivier and Vineet Goyal. Dynamic pricing and assortment under contextual mnl demand. Advances in Neural Information Processing Systems, 35:3461-3474, 2022.
Virag Shah, Ramesh Johari, and Jose Blanchet. Semi-parametric dynamic contextual pricing. Ad- vances Neural Information Processing Systems, 32, 2019.
Jianyu Xu and Yu-Xiang Wang. Logarithmic regret in feature-based dynamic pricing. Advances in Neural Information Processing Systems, 34:13898-13910, 2021.
Yu-Jie Zhang and Masashi Sugiyama. Online (multinomial) logistic bandit: Improved regret and constant computation cost. Advances in Neural Information Processing Systems, 36, 2024.
12

---

Published as a conference paper at ICLR 2025
A
APPENDIX
A.1
NOTATION TABLE FOR THE PROOFS
Table 1: We provide definitions of notations for the proofs.
Uie
ai,t
wi
8*
10ui0a
(1,(P)
P.(
exp(vi. OPL a)
I+Eses, explesa a..
expla O (aP
,eE exp(2 T Or a--w w. (m exp(a))(p).)) (p
I+ Je, (p))) 8 Sp)
(St)
Pt. (i) Pt)
Pt)
LiEs (S.)
(t,(()S,
cxp(2;, (pt) 0)
T+ (xp(25.(05))
=2,r(Pi,t)
T
22 +2 2vCBB |0galln
22,,(Pi T TT
uas
= [xr,,e Oal
dz
Piost
Od
zig.t
O2d
Eies, ut. exp(us)
Q(u)
T+ exp(u;)
Ziit Ej~ a, (195.))))
= 21,((Pr,)) Ej-P, a (5
(,,)
Eies, P.g. (i|S pr) (P. ((EE)
EiEs. Σ Ejes, P., (i)Se, (ilS, (p
H
=
Alza + _ (.)).)
1
(Pt.) 8" 90 (Il,, (P.,)) + | m=
A.2 PROOF OF THEOREM 1
Let 7, be the value of T at time according to the update procedure in the algorithm. We first define event E, {l|Ø, 8*1 H. Br,, vss t). Then have Ey Er-1, ... E₁ and Ey holds with a high probability (to be shown). In what follows, we first assume that E, holds for each t. Under this event, we provide inequalities regarding the upper and lower bounds of valuation and utility function in the following. For notation simplicity, we use U2et == 2.,00, Wi,t == (v..) TO", and x.. := [ Os).
To",
Lemma For t > 0, under E,, for all i E [N] we have
Ustt S Ugit and uis S Untt-
13

---

Published as a conference paper at ICLR 2025
Proof For t, stst f++1 for 2 1, under E,, have
0,,,0, - 2.T,00,(H1) = 1 00 - 2i, 0e1
- || Hr, =110" - 0 ll
dot(HH)
s || V det()),,)) 110- - 0.,1l
< | Hr," VC l1,
- || 1,,7 VV
where the second inequality is obtained from Lemma 12 with the update procedure of (,.(r) in the algorithm. This implies Uz, S Vg,e. Then with Ug 2 0, we have
2 S vi
Under E,,, we also have
lz,,00, D.,.oo,ll = 109, Tg
2.1 0e S | n, 110 1100--00 -elles, S || n,:
which implies
Vie S Vi.--
Now we provide the proof for the upper bound of ug, Under Es, we have
2.,0 - =s,e(PE
0- - 21,( + =1,((t.)) To - -p,( TO 2..(pt T0
- (..( T + (pt,)) T 0. (p(c)) TOy 0-1 S (p(te) TT 0r-
3 pi, P... 0x + +|++11 (p,,
10 o 114,
I (pi,e p,,)),, + Br 12 (p..))))
I (Uit - -xtt) - Br, ||, (pr,))lm,
$ (Va, v2,)) Br, (pt,,)))
s 2VC |0 Br, (2,,
where the third last inequality comes from pi. S Uitt: Pi.t = wto vie 2 nt. and (positive sensitiv- ity) o. < 1. This concludes the proof.
We have
R((S; Re(S.,, P.)
Pi exp(xt, TO) sz.,0,)
Ejes; exp(2,, TT*) S (1),00)
PESt
Pr, exp (p:. (p), 1 21,,0))
(12)
1 S 0,) Ejes, exp( 23, (P (Pie
SES.
Let Vh, = (pt,)) TO + 22 C,, 11,,, (pr:) H. 2/C | M I, Then under E,, we have sco(pi.) (PE.)) S (pt.) T 0", which implies ūa,t wh,r- In what follows, provide lemmas for the bounds of each term in the above instantaneous regret. For notation simplicity, we use ve, (pi,e) f*
Lemma For & > O, under E, we have
ph., exp(2x.(nt.)) T SzT,0e))
Eies, The exp(T(.1) 1 Eies, exp(T(..)
Σ
1 E jEs; (xp(2))(P),.) 10)1(1() TO) & 2),,8))
iES;
14

---

Published as a conference paper at ICLR 2025
and
Eies, uif exp(u(,) 1 Ejes, (xp(2))((31)) ( ((()) I 0,, 1+ Eies, exp(u,,))
Ps. Ps exp(2..(Ph.)) ( S xx,,0,) (pLe
Σ iES
Proof First, we provide proof for the inequality in this lemma. We define A = li E S Pl, S Zica Pi, exp(u.e) 1+2ees exp(14,]"
v,r). We observe that Aj arg maXgg[NHHssss
Then, from Lemma A.3 in we can show that
Agrawal et al. (2017)) and Ui,t S UsSt from Lemmal]
[
EiEr; Pi, exp(us,) 1+ EiEA; exp(us,e)
ΣiEn; Piee exp(T...) I 1 EiE exp(U.,1)
(13)
From the ahove, under F,, we have
Σieny Pi, exp(usr)
Eien; Pi,e exp(Tie)
Eier; tha exp(Ti.1) +1EA;;; exp(T;1)
(s(
1 EiEr; exp(ur,))
1 EiEA; exp(ū;,)
ΣsEA; Tie exp((Tr))
Eies, Viy exp(ui.t)
- 1 Eies, exp(ui,t)
(14)
Lies, exp(u..))
where the first inequality is obtained from (33). the second last inequality is obtained from 1A S dg from Lemma [ and the last inequality is obtained from the policy of constructing S,. Then from the definition of St, as in Lemma H.2 in Lee & Oh (2024), we can show that
Eies, Te, exp( 1+ E.ess exp(u,,t) I
Evss, Ti exp(TT.))
(15)
1+ ++ Eies. (xp(T',.)
Here provide a proof for the equation in this lemma. Since pi, 2 from the policy and tht I th from Lemma we have
Eies. tf (op(ut,)1(0 $ v.)) + Eies. (xp(u(,)) $ v.))
Eies, uh exp(ut,)
Rs Pt)
(16)
I+ EiEiss exp(u(;)
which concludes the proof.
From 12 and Lemma
2 under E,, we have
Re (S) P.,,).)))
pi exp(ex, (o. S 22,,0,) + Ejes; (P..)
Σ
$ (.,,0,)
Ves;
Pi, exp (pr.) 0²) 1))((px (pi. S s27,0,)
1+ EEEs, jES,
1 S 2.)
FES.
Eies, Vie ()
Eies, ut exp(u?,))
1 Eies, exp(TT,.)
1t Eies, exp(u?,)
Eies, Tie exp(T(,))
Eies, at exp(t(.))
+ Eies. et exp(T(.))
Eies. ett, exp(ux,)
1+ EiEs, exp(T(,)
1+ Eies, exp(T(,)
+ Eies, exp(T(.))
1 1 EiEs, exp(u),)
(17)
To obtain bound for the above, we provide the following lemmas.
15

---

Published as a conference paper at ICLR 2025
Lemma 3 For t 0, under E, we have
Eies, Th exp(T.,))
Eies, tif exp(TT,.)
(Br, max || ieSt
1 Eies, exp(Ti,)) 0
Br
1+ Lies exp(T..1)
Proof For T 2 0 anddd t, St t,+1 under Eg, we have
0i - 2i = - 00 - J JT, + (VC + 1)3r, |
=x e 00 + +x, (r, + (VC 1|=,,ll=
= 0, - = TØ + 2 TØ o T0,, + (VV++ + 1)3,, |2qell
110 0-1 |1 + 10,, 0 1|, + (VC + 1
(Hi(
s Br, || H +
10., 00 Il,, |1 (VC+ 1) [ H
det((H..)
22(VC + 11sellas)
where the second inequality is obtained from Lemma 12
Let Ui.e= 21,(( Öz. Using the above inequality, under E,, have
Eies, Th exp(T(,1) Eies, et. exp(T(,.) 1 + Eves, exp(T(,.) 1+ EiEs exp(T((.)
Eies, (UL, 2T,1) exp(T(,))
1+ Eies, exp(T(,1)
Eies, (Ui v2,,) ((.))
1 Eiss, exp(1/,,)
Eies, 2(VC 1) ||,,,ell exp(T(..)
1+ Eies. exp(T),,)
S 2(VC + +1)3,, max || iES.
(18)
Let ž,,t (pi.e) EjjP, a (15 (1 and Ti,e Fz,t Eg-Pe (18t.))) [z,1]-
Lemma For t > O, under E, we have
Eies, tit exp(T(..)
Eies, tft exp(u(;)
1+ Eies, exp(1k(,) + Σ Pr. P() + ( (
1+ EiEs, exp(u(,)
0 82 (max (Pt)))(i max || ( + B2, sES. 1|
(max
max |
iESt
iES,
iESt
VES.
Proof The proof is provided in Appendix A.5
In the below, we provide elliptical potential lemmas.
16

---

Published as a conference paper at ICLR 2025
Lemma
max iES,
22, (pr,))), .1(E)) log(1 (2TK///)))))
max iES:
|R, ((B,) (Ad/k) log(1 (8TK/AA));
P, (iSSss ((E)) 2 ldlog(1 + (8TK/dX)
sE
Proof Define
(..)
Σ
P.. (i) (..
iES.
P ((E))
(19)
JES,
Then first have
(,,),)
Σ (i]Se, (1.
YES.
De 1(E.)
iEs. JES.
Σ iES;
P. L, (..
Σ
(1 + (
YES, JES,
2 Σ
P. a.a St) P.),,
iES,
ΣΣΣPE P. P.a. St. pelessleeeeeeeeeeeeeeed...... =2uu(e:)))eeeee
2
JESIJES
Σ P.o. (i)Se, (p)
VES.
1(E.)
iES
(1- PP (1-E G1S...i) anolo.eeesoppn ((EE))
Σ
P LR,
(i]St.Pr) Pr)
IES,
jES.
Σ YES.
10, (iSSt.p.)Pp
k2 (p..)))).. 1(E.). 1(Es).
(20)
KES,
Define H/: == Al2d + E(-1 (0.). Then we have
Hi = Hi - (..) = Hi +
Σ
(FEE)
(21)
iES.
17

---

Published as a conference paper at ICLR 2025
which implies that
det(H) = -
2 det(Hf} - Σ
(2,, I(E)))
iESt
= dei(HH) det (12d + Σ
kH, 1/2 xH, Zz, (pi,)) " (
iES:
= det(H)) +
Σ
(PI.) ((E)))
1ES
2 det(AAzd)
II
1+
(p1,), (Fs))
k
iES,
2 2d
II
+ max x| 21 1
iES.
s=1
2 2d
II
+ max ki| -
(22)
iES,
Since Pr.s 2it, S S under E,, we have || (Pr,)) S (l + ||w,,11222² < 4. Then under E.. from the above inequality, A 2 4, and < K S. 1, using the fact that æ < 2 logg(1 ( + x) for any [0, 1] and maxtes, (P H:- ((E)) S max,ss, (l3.,((..))1111()))/)) S we have
Σ
max ||, (Pi,))) 1(E,) 2 Σ log #ES.
1+ x max xES:
(pt,e)) H:- H: (Ei)
(E[T]
tE|T]
2 log
II xE[T]
1 x max
(pt,)) 1 2
SES
det(HH(+1)
< 2 log
(23)
X2d
Using Lemma
13 S.l < K, K, 3 AIa+ (P.. ((E,), (p,,,()))))) under
E,, and (Ptt) E R2ad we can show that
det det(H) S (A+ (2TK/d)22
Then from the above inequality, (33 and using the fact that 0 Hi z He from G.(9) 2 0, we can conclude
T
T max ees,
Σ max ie
[ (pr.)))) 1(E)) <
Σ
< (4d/k) log(1 (1= + (2TK/dX)).
18

---

Published as a conference paper at ICLR 2025
Now provide proof for the second inequality of this lemma. Let Fio,t Oa and Wiet Od which implies Zig = O2d- Then we have
(.(O.)
= P.P (1. (i ((E))
iES,
Σ iESUJES;
1.0 (1St..) (.
Σ ieSt
P. L0 (i|S,. p. 1(E))
Σ Σ
L.. (c)
iES.U())) jEStU(Ro)
EurP, pr) [Zi, (pE)))) (E.) E. (119)))))) BexPa) & (appea)))) I(B.)
E (19
2 Σ Peo (i) St, Pt 2 (EE)
iES;
Σ VES,
k (EE).
(24)
Define := Al2a + E (..).. Then by following the same proof steps of the first inequality of this lemma, we can show that
det(H)(+1) 2 2
II
1
k max
| 1(Es)
(25)
sES.
Since, under Ee, we have (F=,,((t,e))le ||2 < || + /ww. < 2 implying that || < 16. Then, from the above incquality and 2 16, using the fact that x S log(1 + x) for any x E [0, 1] and
maxies, || H 1(E,) ((E,E) maxes, (|E.) X < 1, we have
max | 1(E)) 2 Σ log 1 max | 11: ((Ee)) AT(
Σ
*E(T]
= 2 log
II DE(T]
1 +
K max
1 Hr .1(EE)
EES
(dt((H(+1))
< 2 log
(26)
X2d
Since we have det (H(+1) S (A + (8TK/d))2d and x H A He, from the above inequality and 26 conclude
T
T
Σ max
H-
1(E.) <
Σ
max se8,
1l H:- 1(E)) < (4d/k) (8TK//)))))
19

---

Published as a conference paper at ICLR 2025
Now provide proof for the third inequality in this lemma. Then we have
(.)
= Σ
((EE)
VES;
Σ
Σ
P. r.a. P (EE,)
SE JESt
Σ iES.
P. 1.0 (1ss,
E E
P. Sc. pt) P P0 1(E))
(ES,U(t)) jES,U(ta)
(15 (1 (o. (F(E)
EMP., (15 [z. (.
Ea 11.. (E,)
= P.oo (1 2 (EE).
(27)
iESt
Define == Alza E (0)). Then by following the same proof steps, we can show that
del(H)(+2) (2
II
1+ Σ
S.o.
(t) 1(E.)
(28)
YES.
Since, under E,, we have (p.,, I || + ||W;, ll I implying that || I 16. Then, from the above inequality and 16, using the fact that x 2 log(1 + for any x [0, 1] and Eies, P.,, (i]St, Pc) Z. 1 (EE) S maxies, || (E,) & 1, we have
P.. (i|S, PO) E1. 1(E.) 2 Σ log iEST
ΣΣ
1+ Σ P,oo (i) (.), P.)1,.1 1(E))
(E[T]
iES.
2 log
II
1 Σ
P. (i) pc)) 1(E,)
IE(T]
iES.
(det(HHi
< 2lo
X2d
(29)
Since have det (1(+1) (A + (8TK/d))2d and < Hj He, from the above incquality and we can conclude
29
Σ
Pe. (3..
1(P.) S
Σ
P... (i) p.) ( (Fre)
1=1
1=1 ieS.
< 4d log(1 + (87 (8TK/dX)
20

---

Published as a conference paper at ICLR 2025
Lemma 6
T
max Fe, [1 S (2d/k) log(1 + (TK/dA)), 1E8
max | [1 S (2d/k) log(1 + (4TK/dA)), iES:
Σ
L,, (ilS), Pe)l H, S 2dlog(( (4TK/dX)).
IES:
Proof By following the proof steps in Lemma 5 we can prove the inequalities.
Here we provide lemma regarding the probability of the good event E, We define
17
À + 2v/log (2v1+ + 16 (log(2vI+ 2 + 4n
89 = n/(6lg(1 + (K + 1)t) + 6)
16
22 log(1 (t+ 22) + 16A
and for 7 2 1,
17 À + 2 AvAlog (2V1 + 2tT + 16 (log(2V1 +22+2)2) 4n
1 = 1/6log(1 + (K + 1)t) + +6)
16
+2 Gogg + (t + 1)/21) + S2.
Lemma 7 Let c = 2n, A 2 max m 192 84d7}. and = 2 log K + +1) +3. +3 Then for 1 S t2 we have
1
P(E,) 2
T
and r and t, 115t 1,1 have
P(E, 2 T
Proof
The proof is provided in Appendix A.6
Lemma
2 T
I(ET)) > 1
Proof Recall E, (100, 0n B,, Vs < 1). For the time step 1 < < 1,+1 for
T 2 2, since Ej C Eg, C Er, from Lemma
7 we have P(E,EE,) (PE)))) ( 2 7
implying P(E,) 2 (1 T-z (EE,)) Likewise, we have P(E,,) 2 (1 +/) P E E,,-,) We also
have P(E,) 2 1 - 7h for 1 11stt tz.
Therefore, from Tr < T, we can obtain
1
P(E,)) 2 1 1 )
P(Er)= 2
P P(E
1
T2
T
Let X (1 71) T
By using the fact that 1 1
<
log(x) < for x > 0, we have
x
X 1 > log(X)= = Tlog (1 (1- T2
-T
T
1 1-
- 72
= T 1
21

---

Published as a conference paper at ICLR 2025
which conclude that P(E,) 2
T -2-1 2 1 7.
Now we provide a bound for the total number of estimation updates, 77. Using Lemma 13 under
Er, with (Pt,)\)) S 2 and (p,.) E R2d can show that del (X+ (27 (d) Therefore, from the update procedure in the algorithm, Tr satisfies 2 < (TK(()) which implies 7y Old (og(Tg))))) Then we have
B[ = E[ FT (FT) PE)
S Sid K KT) log log K) + E5
<
logloog(T))o))))))) C Civ (T) log(K)
Ö(d),
(30)
where the second inequality is obtained from P(E S 7 and or $ T. Likewise, have
E E[32, EJS?, 1E
< (ogllog(TT) (KT) log) log( K)² ElSe ((E))
s ClPlog(KT)) logg))))))
log( K)² -
Ō(d))
(31)
Then from Lemmas
3
4 5
g
and
(17).
30
31
using the fact that Fj C ..,..., S Eg. we
obtain
(T) = Σ ( - Re(Se.P))
Σ (S vi) R.(S...)) (((Re(Si,r)) (.(S,))))((E))
[E(T]]
AE(T]
(S; pi) - Rc(SE.P)))((EE)) + Σ P(ET)
xE[T]
RE(T]
Σ ies, Th exp(TT..) Eies, exp(TTr.)
Eies, Lt. exp(u())
Σ
I(E.)
+ +0(1)
1 Eies, exp(u?,)
1E[2]
ies, The exp(TT,r)
Eies, Lio exp(TT.)
Σ 1E[2]
Eies, exp(U,,1)
1t Eies, exp(UT.))
+ Eies, eie exp(TTrc) 1+ Eies, exp(TT.))
Eies, the exp(u?,e
((E))
+011)
1 Exes, exp(u?,)
22

---

Published as a conference paper at ICLR 2025
0
E
PTT
max iESt
| [ + Σ
P.o (i)Ss, (1Taellmn, (Baxlllo:)) I(E.)
1E
BES
| ( (c0s))
+E
3
max IESs
max IES;
max iESt
|
max EES.
LE|T]
0
E
Box VT
max IESt
I H.. + Prr
ΣΣ AE(T)
c.. pi)
*E(T]
- 1
Σ
P.
H..
Σ E
P.o. (ilS,. pi)) I(E,)
+
K
iES.
AE(T)
ds B|Brr| dTT/K
ds
8//2
A.3 PROOF OF THEOREM 2
Let Ti be the value at time according to the update procedure the algorithm. We first define event E, {110, 0" ||, < Br, Vs < 1). Then we can observe Er C Er-I,..., C Ei and P(ET) 1/T from Lemma 8 From Lemma I under E,, have
2 S 01
(32)
We let 7/- = Br, / lod Mf) and filtration Fi-1 be the o-algebra generated by random variables before time f. In the following, we provide a lemma for error bounds of TS indexes.
Lemma For any given Fr-1, with probability at least 1 - 0(1/(3)) all E [N], we have
[0 2T,0o.ll S Vell Tello,eelle and āū,, 21,((pr.)) Tol (07)((1 || (lm
Proof We can show this lemma by adopting proof techniques of Lemma 10 in Oh & Iyengar (0199) We first provide proof of the first inequality in this lemma. Given Fr-1, Gaussian random variable
T glm) has mean Or and standard deviation Br, | Let m' = arg max x (m))
Then have
max 01 x.T00l1 mE[M]
(0 ( 0.)
L Mo, 1/2 1/2 (ō.n²)) 0.)l
11
S 3r, || || 11. 22 (0!!z)) 00)l2
max Br, M I|l
|| H1 1 (ō.m.) 0.)11
[M]
Br, 1er, Meeeellle,
max mll,
ME(M]
where each element in Eu. a standard normal random variable, which concludes the proof of the last inequality in this lemma from maxme]Mi | 5 V4dlog(Mt) with probability at least g
23

---

Published as a conference paper at ICLR 2025
Now we provide a proof for the second inequality in this lemma. Let arg max ma(M] 27,000m mm Then we have
max Zi, (1,e(pt.)) T((m)) (pi,)) 0p. 8C7j.al mE[M]
((,)()))))) T (0)m²) - -0:) 30 (( 0w,e)l
(=,,(Pt,r)) H, 11.1/2H1 H|, (0/ 0.)1 80 /,,,
1/2 H 1 (mml) 0,,,)l
I V2 |1 (Pt,) (P., |1(23,,,) /1,22110/ (0(mm)) 10 0.)122 8C3, || 11 (0,2(000))) f2,
I 22 12,, (2,, 1r. max mE[M]
[1(v2,,,, 1 H. 12 (0)m) 0.112 -8)1l2
+ +800,, 11,,,
max mE[M]]
|1 1 H v.t.
(0(m) 02,))l12
-23,, (z (Pt, n,
max mE(M]
Il 2| + 8C 10: max ||5,m112. (E(M]]
where each element in S. and fu. standard normal random variable. We use the fact that 1l S / (t) and Ilsumlll2 I (odlog(t) with probability at least z.. By using union bound for all m E [M], with probability at least - O(1/12), we have
max (p(e) O.m) (pt,)) me(M)
< (V8dlog(M1)) Br, s 88Co((le, + [luulla;;))
8C (oceellat
which concludes the proof.
For notation simplicity, we use uh, = cx We define =; = (i S Pl. S m.,). As in and (6). under Es, we have
R,(S Pe(S
EiEA; př exp(us,))
Eies, 1i (xp(u(,) S v.))
1 DiEA; exp(ur,))
1 Eies, exp(u 10 S v..)
ΣiEA; Via e
Eies Ui exp(u 1 S v.)
1 1 Eien; exp(un,)
+ Eies, exp (u ( S a.)
ΣiEA; UhA exp(ui,)
EiEs, Li exp(u?,)
(33)
1+ Eiea; exp(ur.)
Dies, exp(u?,)
In what follows, we provide several definitions of sets and events for the analysis of Thompson sam- pling. Regarding the valuation, we first define (Q.) max T. for O,, (o!")
Rd) Immea and define sets
θ,,t- {0r- E HddM (,.)(O.)) (0((0)))x,,,00.)))
01,.0.1 S A.laaalla Vi [NI] and
, = 0r E RdxM :.,((() 2 via Vi E [NT] nō.
Then we define event E., (101m)) IEEM E @.,1)
Regarding the utility, we define (,, θ,) maxme[M) (p..)) ((o!") - To..) for O,, (0(m) E IR2dd m and Q.. =0!")) IRd) }e{[M)]
T max 2i, (p,,) Tg(m) +
24

---

Published as a conference paper at ICLR 2025
and define sets
+ = O. Ou x O, E 2R2xMM
x RRdxM T.. θx) - =.o()t)) T0:
I 180hm(12sssp)eellle + : Vi [Mj
and 6 = { n O E R2dxM x RaxM (0. uA vi [ nō. न
Then we define event Eu,t ((0(-m) mmE (00m) IME[M]] 6/ For the ease of presentation, we define E, Ee,e Eu, In the following, we provide lemma that will be used for following regret analysis. Let Zi,e = (p(a) Ej-P,E, (188.)))).. (2.. and Tha = Fi, - Ej-P, P. (-15c.p.) [2).
Lemma For E [T], under Eu,, and Er, we have
Lies, Ui, exp(ūn,)) Eies, ti exp(ū,, θ.)) 1 Lies. exp((i,t) 1 Eies, exp(ūs,,(Quu. +₂))
sup e e.
=0(ni (max (max [Fc iES.
max | || (1m Tt sES.
(max
| || H. + max |
VES.
n Σ P.o.
|| m max [ms,e lES.
iES.
Proof We define Th, = (pi:)) +00r((22(000)))ll: + [[xelll, Then from E.,t and E,. have
U4 S (p(.) To, + sCr(lle,, + |/r
- (,,()))) To + Br, ( 80%((122s((id)llle + (aarel
$ T
From the definition of S. have The 2 i S, This is because if The for some i [N] then & S,. Then as in (15). we can show that
Eies, Tie exp(ūi,)) 1+ Eies, exp(ūr,r)
Eies, Ti, exp(Ti,)
< + EiEss exp(i(,))
Then we have
EiEs, The exp((re)
Eies, Eit e0, 0,))
1+ Eies, exp(ūx.)
1+ Eies, exp(ūn,(0,, 0,))
Eies, Viat exp((ka)
Eies, ut exp(iir 0.))
1 1+ Lies, exp(((,)
+ Eies, (xp O.))
Eies, Ui exp((,)) T+ LiEs exp(i(,r)
Eies, et exp(T(.)) Eies, exp( + 1 Ete,, exp(1?,,)
Etes, st exp(
Eies, eit, exp(ū,,(O,,, 0.))
1 Eies, exp(Tr. +.))
(34)
We define Th.t (p.a) 0c Then, for the first two terms in the above, we have
25

---

Published as a conference paper at ICLR 2025
Eies, Bie exp(
Eies, Life exp(((,r)
Eies, 27,1 exp(
1 + DiEs, exp("iit)
+ Dies, exp(1i;,)
1 Lies, exp(11
Eies, (Ürt - En,1) exp((p()
Lies, (Ris)) - xTTDDuall + |0, La exxx)xx(((()) exp(((,)
S
1+ DiEs, exp( ((,))
1 Dies, expl (xp((().)) (7,,.)
Lies, (xt B,) B,)l exp(T),))
Lies, 2% 17,110,,1111,, exp(U(,1)
S
I 2%, max
|| ,
1 Cies, exp("),)
1 +iEss exp((%,))
IESt
(35)
For the latter two terms in (34), by following the same proof technique in Lemma and using the fact that [//,e ū ( Ow) 7724 21,( To 0.1 + (=,,(Prt,e) T0 ( 2
(1=spll)) H.' + ||assellH..! from E, and O x O E Ô. with Br S Te. we can show
that
Eies, 2it exp(TTe)) 1 ++E exp(i(..)
Eies, Eir (xp, 0.))
sup G.
1 Eies, exp(ūr,,(Ou.. +.)
=0 10(7((1g) (max YES, (1a,) max | (am:)) 72 (max | H. iES.
[ 1
H
kES;
t (t SE
+ (
(36)
We can conclude the proof from
34
35
and (36)
Then, for a bound of instantaneous regret of 33
we have
EiEr; Uie exp(ur,)
Eies, wit exp(u(,))
E
E
((E)) Fi-1
+ EiEsp exp(ui,)
1+ Eies, exp(u?,)
Eien; Uie exp(ui,))
Eies exp(", 0.)) ((E,) FF-1
E
E
inf e 0.x,,E6, SCINSSSS 1 Eies (x,, (0,,
EiEr; exp(ure)
Dienz Vie exp((r.))
Eies vt exp(ūi, 0.))
E
E
Eier; exp(ure)
e e.x SCINHSSSK 1 Eies exp( (O,, 0.))
inf
max
1(E)) F E.
CKEa Di,1 exp(ūx.))
Eies, utt exp((x, 0,))
E
IE
inf e, x,,,600 I Eies, exp( 0.))
1(E,) [F,1, E.
Dier exp(ūr.))
E CREA; Tie exp(ūr.)
EiEs, ut, exp exp(ū, 0,)) inf e xB,E6, 1 Eies, exp( (O, 0.))
E
I
1(F.) [r-,1, E
EiEr, exp(ūn,t)
Eies, TH. exp((r,))
Eies, Lh. exp( O 0.))
E
E
inf e.xe.Eō, 1+ Eies, exp (x, ( 0.))
1(E.) F E.
+ Exes, exp(ūr.))
Eies, The exp((rr)) 1 Lies, exp(ūnre)
Eies, vi. exp(pp (m,, 0.))
E
E
sup
1(E,) Fi E.
1 Eies, exp ( 0.))
X..EE..
0
E
E
(max IES.
2| (p..))
max bes,
|oo lP,. (max | 11 sES,
max
| 1)
iES,
l 1 ((E,) Fi-1 Fig 1)
+ Σ
P (1) (1) + ||T (xp:) + max tES.
NES,
26

---

Published as a conference paper at ICLR 2025
0
ne (max ( + max iESt
| H.? + 76
(max RESt
|| H, + max
| :
iES:
IES:
+
Σ
P.. (1 Px) P() + || +1 + na max sESt
| m Fe- Er, Er x Es
S
0
E
E
2 (max 7t
|| (2t,
max RES:
||ss,e (mm + 7e
(max
+ max iES:
| (
EESt
VES.
| [e-1, E,, Es P(E))--)))
+
Σ
P. C.o. P.) + [ 11 +
max xES
(37)
where the first equality comes from the independency of Fg given Ft-1, the second inequality is obtained from 41 S Uh, under the event E, and from the definition of St, the third inequality is obtained from the fact that v S a.i under E, the third last equality is obtained from Lemma 10 and the last equality comes from independence between Eg and Eg given Fi-1- We provide lemma below for further analysis.
Lemma 11 For all t E [T], we have
P (ot 2 Vi and uية 2 u4 Vi [M] Fi-1, 2 4VeT
Proof Given F TTT O.r
alm) follows Gaussian distribution with mean 0,, and standard deviation
Br, [[aa,ellln Then we have
max x (T MEIM
2 22,000 Vi [M]IFE11, E.
NTP
J. 1.,,0um g(m)
xr,,00 Vm [M] [M]]Ft-1 FA)
vst
0. I.T Vm [M]]Fr-1, Ee
2 NP Zm
Br, Ji,e| H
1 - NP (Z 1)M
where 7m and Z are standard normal random variables. Likewise, we have
max 2g,1 (pr,e) miE[Ms]
+ SC max (Tma) v.t. -1 (.T. 2 2.,(p) Vi [N] Fi-1, E.
M
max Zz,1 (pi.)) mm + 8C (0 0.3 - T.T Bo,t) 2 2. Vi E [N] F Fg M
((m)
2 1 NP
(p,(P) T((m)) + SC
g(m) - x x..D...) < <,,((ri)) T Vm E [M] Fi-1, Fa))
(p,(() Topm))
(p,() T (x
H(m)
x Dv.c) 0.
NP
Pr, 211 1i (ptt.)) 11 11 + 8C' |i, H,
Br, 21 (P.,) -.- + 8C |01| H
x
3r, (112,,
+
ene(pt)) - T
Vm E [M] Fr E,
(l( +2/ 11
8,
27

---

Published as a conference paper at ICLR 2025
Br v 2 (2 +80 F H..e
- NP
Zm
Br. (2,,1, 17 22C1 2
2,((1,e) TM (p,()) To.
vm [M] Fi-1, Ei
3r, (12t,,))))))), + +=
(P -z.(p.)))))
2 11 - NP Zm (1. (2. (P.))ll) + 2VC||ar,,lly..!
Vm E [M] Fi-1, Es
2 1- NP (Z <1)
where the third last inequality obtained from the fact that the variance of zi, (pt.)) 0.ml) (P,( 0g 8C(x,,, 0 ,T,,00. 0.,)) is 88, (2) (P())))
8CI|=,,, H., 1) and second last in- equality obtained from /2(a2 + b2) 2 (a+ b), and the last inequality is obtained from Uset S Us in Lemma D and independency for M samples.
Then using union bound, we have
P ( 2 Vie and ūū, 2 uset Vi [1]] E.)
2 1 2NP (Z 1) 1)M
2 1 2N 4ver
M
Aven
where the second last inequality is obtained from P(Z < 1) 1 1/4yeT using the anti-concentration of standard normal distribution, and the last inequality comes from M =
log( e/ This concludes the proof.
log 2N 2N
From Lemmas and for t 2 to for some constant to > 0, we have
P F(E Ea)
P Tiat 2 ui,ts Viet Uiet Vi E [N] and (0am)) (ole))mm IEE(M] &r,t, ( ImE[M]] ( ImEL E @.,1Fe-1, Fr)
P Piūr, 2 Wi,t, Ti,t 2 vi Vi E [N]] Ex)
PP (0(m)) ImElM] & θ. (0(m)) IIE[M]] (0lm) J ImEl F Ei)
1/8VET.
For simplicity of the proof, we ignore the time steps before (constant) to. which does not affect final result. For simplicity, we also use
Le = (max (l,.,(Pt..)) H, + max iES,
||x,,el| (....el(a,.))) H..! + 78 (max
|| 1| H,
+ max
(T,,ell2.. H..
zEs:
iESt
+ %/ Σ (d P.) p.). + +I + Te max xES,
(i)
| |
SES;
Hence, we have
BLL Fr-1, EdJ > E Le F.-1, E., Ee P(E,)F--1,
> E
Le Fi-1, E,, Eo] 1/8VeT.
(38)
28

---

Published as a conference paper at ICLR 2025
With (37 and
38
we have
E EiEr Vi, exp(us,t)
Eies, tfe exp(ux.))
E
((Fa)) Fe-1
EiEn; cxp(ui,))
1 Lies, exp(ux.))
0 E Le Fi-1, 1 E., Ed
P(E | Fi-1))
0 (E Le Fr P(E, Fi-1)).
(39)
Then from
33
39
30
31 and Lemma 5 66
with EG. J Eg - C Ef, have
Rd (T) = Σ (S p.) - (())) + Σ ES - (((S)))))(EE))
KE[T]
KET
ai Pia exp(ui,)
Eies, Lit, exp( (0 (pp(,,,) [ S ((ie))
1(F4)
+ Σ
P(F
+ Σ rEA; exp(ui.t)
1 Eies. exp(uf, 1 S v..))
1E|T]
EE
Σ EE(T]
[Le FI-I, 1
Σ LE|T]
E [(,)
E
Vd VT
Σ
max
|| m!:
+Vde
ΣΣ AE(T) iES.
P.o. (i)St.
sES.
KE|T
Σ Σ
P. r8
Σ Σ KE(T] VES.
P... (i|S, Po) E ((E)) )
+ & E[S,g]
H.d
n
KE(T)iES.
B B|3ra Jd T/K+ / d²
= δ d VTTTK + )
A.4 RANDOMNESS IN ACTIVATION FUNCTION
In this section, we study the case where there exists randomness in the activation function of C- MNL. Let Si., be a zero-mean random noise drawn from the range of [-c, c) for some 0 < c S 1. Then the noisy activation is modeled in C-MNL as
exp(2x,(PL.)) 1 TO S (xTe0p + +) (.(....))) I+ Ejes, exp(23,((3..) 0*)1(P; S (x),00 + C),)++
A.4.1 ALGORITIM & REGRET ANALYSIS
Here we provide an algorithm (Algorithm 33 for the random activation C-MNL. The different part from Algorithm is in pricing strategy such that Pi, (w c The remaining parts are the same.
Now we provide regret bound of the algorithm in the following.
Theorem Under Assumption the policy of Algoritim 3 aachives regret bound of
R7T (T = ō ( (d² T TTK++(T))))))
29

---

Published as a conference paper at ICLR 2025
Algorithm 3 UCB-Uasee Assortmment-selectioon with Robust-LCB Pricing (UCBA-RLCBP) RLCBP)
Input: X, 77, C
Init: 7 5 1,4, f- 1, (1(1) f-0, 0.
for f l...., do
H₂ - N2zd + E. Gz(O.) + (G with 3
H2 - Al2d s=1 (3,) with
Ha,1 + Ala + E.=l Gr (6.) with
O, arg mingee Dr (r(0 0 27 10 0
with 2
D Estimation
if (et) > 22ee Hr, then
7+T +1
0 (m.(r)= + Bu,1,(= (111))
io [ do
Ei 0,,00.(7) /233 /2
LCB for valuation
Pi, (Uit -c)+
Price selection w/ LCB
U. + 00, + /Bel(Fi,ellH.2
> UCB for valuation
The Zz (p..)) T0, + (ellz,,(Praa) 2228 t UCB for utility Bi. exp(a,))
S: c arg max DAN Eies
Assortment selection w/ UCB
T+E explaga))
Offer S. with prices p: = (pi,tlies
Observe preference (purchase) feedback Vi. {0, 13 for S,
Therefore, if we have = O(1VT), the regret bound in the above theorem becomes Ö(d /T/k) same as that in Theorem the case without the noise in activation functions.
| Let 2i, (Vi, - c) and Wifee = Zz, 0t + 22/28 (Pt.))) + +2/28, || [H + Then we can observe that under E,, Pi,e I Ui, + Gi, and ūh S wh,,- From
Proof Here we provide only the different parts from the proof of Theorem
12 and Lemma 2 under E,, we have
Re vi) Pt)
Eies, Vi, expppxpp (u()))
Eies, oit exp(T((.) 1 Eies, (xp( + Eves, eff exp(T((,)
Eies, oft exp(ul,) 1 Eies, exp(u),)) (40)
1 Eies, (xp(())))
Eies. exp(xt(,)
By following the proof of Lemmas
and under E, we can show that
Eies, T exp(T(.))
Eies, of exp(T(,e) 1 Eies, exp(T(.))
(a)
1 + Eies, exp(TT..)
-0 (0
Bh max FES,
|2 H.d + B2 max || (Pr.)) + B,, max iEs;
||
+c)
iES,
E Eies, eitt exp(TT,)
Eies, Lif ot
exp( u.,))
(b)
1 + Eies, exp(TT,.)
1 Eiess, (xp(u(,)
= 0 82, (max
(Z + max | H.:! ) + 32, (max BES.
H, |
+ max
|| 1 H.!!)
YES.
bES,
VES.
+Br,
Σ (18.
| m..! +
VES.
Then by following the proof steps of Theorem
we can show that
RR (T) = δ d T/
K
30

---

Published as a conference paper at ICLR 2025
A.5 PROOF OF LEMMA 4
Here we utilize some proof techniques in Lee Oh (204)). Let Q(u) = Lies, wie exp(ui) I+2ics, explu:] and np = [ue, : E St]. Then by applying second-order Taylor expansion, there exists & = c)uf + cT! for some E (0, 1) such that
Eies, ofe exp(u',)) 1+ Lies, exp(T(,.)
Eies, thi exp(uf,)
1 + Eies, exp(u(,c)
= v.Q(uf)(T(.. - up,,) 2 EE JES
( - u ( uf.))
(41)
ES
Let Zin.t = Og and Wio,t O2 implying zio,t = O2d- Then for the first order term in the above, we have
KES.
Σ (ut -.+,)=
Σ (t) ul,))
iES.
WES
Σ
2VCB Pr. (v. (I |
iES.
Σ 2
+ ll?
LJES
Σ Pr,(u))
VESt
Σ P=:(0))1::: + [oreella jeS.
Σ
P3,((uE) P=((ul))os::llaa
jES.
For the first two terms in the above, we have
[Z -
Σ Psoolllleae
JES,
Σ
P.
JEStU(io)
-IRas(Ph - Ej~Pan (1S.p)) (1
< (pL.)) (1Sa. (z
H
< (3.)(P)))) Ej~Pr ( (mm)) (3)0(P H
where the first inequality obtained from Jensen's 's inequality and the last inequality is from ||a]| l|a b + bll < |aa bll |||] By following the proof steps in (H.1), (H.2), (H.3), and (H.4) in Lee
31

---

Published as a conference paper at ICLR 2025
& Oh 2024)
show that
Σ
" Pr,((u))
(2,((PL))) By-Ps (19mmm)) (35:((15e))] u,
iES.
(,,)(ug)
(p.(p)))) - Bj B (-1..p)) (3)x(D3ee))
= =0 max
Br
(.L. + Br, max iES,
||,, H,
EPO P.o (is...))ll.
iES.
sES,
where the first incquality is obtained from 0 S E I under E.. Then, likewise, we can show that
Σ EES
t Pre(F)
Σ P,a((u))lzs,,ll jES.
[ Eymeeor (1St.p)) [3 H Pu,(up)
iES:
= =
Br. max
| ( + Br, max seS.
[ | H + (i PiSs)
sES,
SES,
Putting the above results together, for the first-order term, have
Σ v.Q(u))(uk, m2,s)
iES.
=0
32 (max (. + max sES: || (1r-:) + B², (max SES
|12,,1177. + max
|| 11!!))
?)
IES,
sESt
+Br, Σ PLo (() + 1 IES.
(42)
Now we provide bound for the second order term. By following the proof steps in (H.6) in Lee & Oh 2024) with 0 I zt.. S under E,, we can show that
(uh,a - un V. une)) o ( (B
(max (,,,)) + max iES
2
iES.
KJES.
(43)
Then we can conclude the proof by 41 and 43
A.6 PROOF OF LEMMA 7
For st 122 1, since Pa. from the algorithm, we have ye P:(-ISt, pt) Pt, (-(St. Pt). Then from Lemma in Lee & Oh 2024), for S t S t22 we can show that P(E,)
7
Now, we provide a proof for the time steps t, + 1 S t S tr+1 for r 2 2. We utilize the proof procedure Lemma in Lee Oh (002)). The main difference lies in focusing on the conditional probability for a good event in our proof. Under E,,, for f S t S fr+1 - 1, since Ei, S Ug we have Vi. Pp P.(.)S(,pt)) = Pt.o- (t)S Then from Lemma F.1 in the previous work, we can show that for t, + 1 < t t.+1, with 17 = log(K + 1) + 3 and A 2 1, we have
1-1
010 0 12, < 2n
Σ +=
fs(0') - ss(0 + 110., 0'112 + 96v2n Σ 10.+1 0.13 s=t.
10 - -0.122
(44)
32

---

Published as a conference paper at ICLR 2025
Then from Lemmas 14 and 15
for any
0 with À 2 84d7, show that with probability
least 1 6,
Σ 1s(0)) [o (0(0)
smt,
17 A + 2v (2v1+ (2V1+ - 16 (log(2V1+ [lbg(2V1++/00)3 + +2
(3log(1 + (K + 1)t) 3)
16
Σ 10, 0sti 112, 22Ged + (1+ 1)/2A).
(45)
2c
By setting c 2n and with A 2 192,2n, we have
t-1
1-1
96v 2n
10++1 - 0.12 + (2 - Σ
100+1 - 021122.
smir
s=
t-1 10a+1 0.112+ + (1-1) Σ
96v/2 2n
Σ
110+41 0.11
s=tr
==
19v 2n
11 - 02 12 S 0,
(46)
s=t.
where the first inequality comes from H, 2 Al2a. Set = 1/T
Then under E,,, from
44
45
46 with probability at least 1/T2, we obtain
100 - 1'1
$ (og(1 (1+ + (K + 1)8) 6)
=
17
À + 2v (2V1 21T + 16 (1og(2(1+21799)) + 4m
16
+ 4yy66ed log(1 + (1++ 1)/2A) 110,, 11'1,
17
x + 2V (2v1 + 21T + 16 (log(2v1 (lo((211+2T99)) 21T31)²) + 4n
S <66logg(1 + (K + 1)() + 6)
16
+ 4cy + (t 1)/2A) 3 37+1-
Finally, we can conclude that, for < t < 12, we have P(E)) 2 1 A/. and for 2 2 and
tr + 1 s tr+1. we have P( E, E,,) 2 1 77.
A.7 NECESSARY LEMMAS
Lemma (Lemma 12 in Abbasi- Yadkori et al. (2011) Let A, B, and C be positive semi- definite matrices such that = B + C. Then we have
x T Ax dct(A)
sup #
x Bx det(B))
Lemma 13 (Lemma 10 Yadkor- al. (0111) Suppose X1, X2...., X2 Bd and for any < St.. ||aella < L. Let V4+1 Xl E.=1 X,X] for some X 0. Then we have det(V441) 1 (A /
We define 02(2) 5 + R such that [or(:)]; = exp(x.)
1+E31, exp(s,) We also denote the probability
of choosing the outside option as [ot(2)]o 1+ explas)
with in == 0. We define pseudo-
inverse function of ox(-) such that a (p)) p for any q E {p [0. 1|lellllll < 1). We
33

---

Published as a conference paper at ICLR 2025
observe that of R I where (r((4)): log(9: 119111)) for any 9 {p [0, 11ss|11ppplp < 13. We also define on = o (B (Bw-<r,lo.(2z.. (p, :.s, )1) and P. NV (1 +
)H for a positive constant 0. We define Je(2,y) = Σi= 1 (vr,e) log( [o)())] Then we
have the following lemmas.
Lemma 14 (Lemma F.2 in Lee & Oh (024)) Let d E (0, 1J and 2 1. For > 2 and 4, + 1 S t S br+1, under Ex,, with probability at least have
5.0' Σ Js(ss)ys)
17
x + 2v 2vI+ 21
2v 28 ))
< (3log(1 + (K + 1)0)+
+ +6 log
+ 2.
16
8
8
Lemma 15 (Lemma F.3 in Lee & Oh (024)) For any c > 0, let X 2 max 72ed]. For 5 >
and t, + +1 1st tr-1, under E,,, have
Σ Us) f0(01)1) s
Σ 10, 0s+1ll2s + Voed (1+
t+1
2c
2A
34


Reviews:
[{"review_id": "MijcGiSvkM", "reviewer": "Reviewer_3kB4", "summary": "The authors study the dynamic multi-product selection problem. They introduce a new censored multinomial logit (C-MNL) choice model, capturing buyer behavior by filtering products based on price thresholds. They propose two algorithms that leverage a Lower Confidence Bound (LCB) pricing strategy, combined with either an Upper Confidence Bound (UCB) or Thompson Sampling (TS) approach for selecting product assortments. Both algorithms achieve provable regret upper bounds, and their performance is further validated through simulations.", "questions": "1) Line 174: \"Then we define an oracle policy.\" Could you clarify if approximate regret is considered in cases where the oracle is based on an approximation algorithm?\n2) Line 347: \"Additionally, our regret bound does not contain $1/ \\kappa$ in the leading term\". Could you provide some intuition or high-level explanation as to why the term $1/ \\kappa$ is absent in the leading term of our regret bound? This could help readers better understand the underlying reasons for this distinction.\n3) It could be interesting to explore whether the LCB-based valuation strategy for pricing can be effectively integrated with product selection methods other than UCB and TS.\n4) Section 6: Including examples of real-world applications would enhance the discussion on potential extensions.", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "1) The censored multinomial logit (C-MNL) model is a novel approach that effectively captures buyer behavior by incorporating a price threshold for product selection, reflecting realistic purchasing patterns.\n2) The authors introduce an innovative Lower Confidence Bound (LCB)-based valuation strategy for pricing, which can be flexibly integrated with various product selection methods to support this new model.\n3) The authors provide comprehensive theoretical analyses, deriving regret upper bounds for both proposed algorithms. Moreover, these algorithms are computationally more efficient than previous methods", "weaknesses": "1) The algorithms involve several input parameters, such as $\\lambda$, $\\eta$, and $C$. However, the paper lacks guidance on how to select appropriate values for these parameters and does not discuss how they impact the regret bounds.\n2) There is no lower bound analysis on the dependency on $d$, making it uncertain whether the proposed algorithms are optimal.\n3) In the TS-based algorithm, the prior distribution and prior knowledge used (e.g., Gaussian distributions) are not clearly discussed, leaving the assumptions about the prior unclear.\n4) The experimental setup is relatively limited, with tests conducted only for $K=4$, $d=2$, and approximately 20 arms (products), which does not reflect the scale and complexity of practical applications.", "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": "yhPdaNlEwj", "reviewer": "Reviewer_8pM9", "summary": "This paper studies the problem of online pricing and assortment optimization, where a seller engages in repeated interactions with a buyer over $ T $ discrete time steps. In this setting, the seller offers a selection of products from a set of size $ N $. At each time step $ t $, the seller chooses an assortment $ S_t \\subseteq [N] $ of products to present to the buyer, along with a specific price $ p_{i,t} $ for each item $ i \\in S_t $.\n\nThe buyer is characterized by latent parameters $ \\theta_v $ and $ \\theta_{\\alpha} \\in \\mathbb{R}^d $, which influence their purchasing decisions but remain unknown the seller. Each product $ i \\in S_t $ is associated with known feature vectors $ x_{i,t} $ and $ w_{i,t} \\in \\mathbb{R}^d $, representing various characteristics of the items. The buyer's valuation of a product is given by $v_{i,t} =  x_{i,t}^T \\theta_v $, while their price sensitivity is described by the parameter $ \\alpha_{i,t} = w_{i,t}^T \\theta_{\\alpha} $. Consequently, the buyer's utility for a product $ i $ is defined as $ v_{i,t} - \\alpha_{i,t} p_{i,t} $. The buyer makes a purchasing decision based on a \"censored multinomial logit choice function,\" which acts as a sigmoid function applied to all items $ i \\in S_t $ for which the price $ p_{i,t} $ does not exceed the buyer’s value $ v_{i,t} $.\n\nThe goal is to minimize regret compared to the optimal assortment and pricing decisions in hindsight. A key challenge is that the seller lacks information on which products are \"censored\" by the buyer's multinomial logit choice function (i.e., $v_{i,t} < p_{i,t}$). This uncertainty makes it challenging for the seller to glean information from the buyer's purchasing behavior. To address this, the authors employ a combination of algorithms: a Lower Confidence Bound (LCB) approach for setting prices and an Upper Confidence Bound (UCB) method for selecting assortments. By using the LCB algorithm, prices are initially set low, reducing the likelihood that items will be censored in the early stages. This enables the algorithm to gather more accurate data on the buyer's latent parameters, $ \\theta_v $ and $ \\theta_{\\alpha} $. This algorithm obtains a regret bound of $ O(d^{2/3}T^{1/2}) $.", "questions": "Please address the confusions I highlighted in the Weaknesses section.", "limitations": "", "rating": 6, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "-\tThe paper offers a natural extension of the multinomial logit (MNL) model, building on previous research that has explored online pricing and assortment optimization for the MNL model without incorporating censorship. Censorship seems natural and adds interesting additional, combinatorial challenges.\n-\tAdditionally, the proposed approach, which combines the LCB and UCB algorithms, feels intuitive and well-aligned with the problem.\n-\tFinally, the paper well written.", "weaknesses": "-\tIncluding the Thompson Sampling (TS) section should be more thoroughly motivated, especially since the algorithm’s regret is weaker than that of the LCB/UCB approach. From the paper, it’s unclear what advantages TS offers over the LCB/UCB algorithm. If none, this section might not be necessary and could be removed to streamline the paper.\n-\tAdditionally, I would appreciate a more detailed explanation of why the latent price sensitivity parameter $ \\alpha_{i,t} $ is essential to the model. It would be helpful to have some real-world examples that illustrate the importance of including $ \\alpha_{i,t} $. Moreover, I find it counterintuitive that $ \\alpha_{i,t} $ appears in the exponent of the MNL choice function $ \\exp(v_{i,t} - \\alpha_{i,t} p_{i,t}) $, yet it does not appear in the indicator $ \\mathbb{1}(p_{i,t} \\leq v_{i,t}) $. Intuitively, it might make more sense if the indicator were formulated as $ \\mathbb{1}(\\alpha_{i,t} p_{i,t} \\leq v_{i,t}) $, as this would more consistently capture the influence of $ \\alpha_{i,t} $ on the decision threshold.", "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": "tcK2dUtAzn", "reviewer": "Reviewer_GGxS", "summary": "This paper studies the problem of dynamic multi-product selection and pricing. In such a problem, the seller must not only set prices but also determine which products to offer. The authors introduce a LCB-based pricing strategy to set prices, which can promote exploration because buyers would be more likely to purchase, avoiding the censorship issue. As for product assortment selection, they employ two strategies, one based on UCB and the other based on Thompson Sampling. Each strategy corresponds to an algorithm with a guaranteed regret upper bound. Extensive experiments on synthetic datasets validate the performance of the algorithms and demonstrate their superiority over existing approaches.", "questions": "This paper proposes two product selection strategies, which makes the theoretical results of this paper look more fruitful. Give the regret upper bound of the TS strategy is worse than that of the UCB strategy, is there any more benefit to studying this strategy besides being able to announce that \"it is the first work to apply Thompson Sampling\"? For example, is the TS strategy more convenient in code implementation? Or is there an advantage in computational complexity? ...\n\nPlease compare the two strategies in detail. The rating may be reduced if the answer is insufficient.", "limitations": "", "rating": 8, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "1. The problem studied in this paper introduces product assortment selection in a multi-product sale scenario that has not been considered in previous work.\n\n2. The theoretical results are very solid and accompanied by experimental validation. I really appreciate the proof sketch in the main text, which shows the authors' very clear proof ideas.", "weaknesses": "1. According to my understanding, proposing a framework implies proposing a class of solutions. The authors' real contribution is to find a problem - a problem that fits the actual application scenario - and formalize it, so it is inappropriate to describe it as \"proposing a novel framework\".\n\n2. I know it is difficult to find and prove a regret lower bound in such a complicated problem that involves both price setting and product selection, but a complete paper should at least have a discussion about the regret lower bound. Perhaps it is to refer to the magnitude of the upper and lower bounds of other similar problems, or perhaps to propose a conjecture of a tight regret lower bound, so that readers can have a clearer understanding of the difficulty of this problem and the contribution of the authors.\n\n3. No experiment on any real-world datsaet.", "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": "flXFJ25lB5", "reviewer": "Reviewer_Ues7", "summary": "The paper considers both multi-product selection and pricing under censorship. The authors use a new way to find sublinear regret that uses LCB to price items and UCB/TS to select assortment. They achieve optimal regret bounds with respect to $T$ and use some simulations to verify though lacking comparable benchmarks.", "questions": "For the TS, you use the maximum of m samples. Then, with high probability, $x^T\\tilde\\theta^{(m)}$ is larger than the mean. It's somewhat another kind of UCB rather than a \"true\" TS. Do you have any other intuition or motivation to use TS? Can it reduce computational complexity compared with UCB as it still contains a hard-to-compute argmax?", "limitations": "", "rating": 6, "confidence": 3, "soundness": 2, "presentation": 3, "contribution": 3, "strengths": "The way of applying LCB to pricing (actually exploration) is inspiring. The extension from MNL to C-MNL is practical in the real world. The usage of TS is quite innovative.", "weaknesses": "1. My main concern is the statement that $1/\\kappa=O(K^2)$. Is it true? If $|S|=K$, since exp>0, we know that $P(i_0)\\le1/K$. In the meantime, choosing $i$ with the minimum exp term, it seems that $P(i)\\le 1/K$ as well. Therefore, $1/\\kappa\\gtrsim \\Omega(K^2)$. Please let me know if I missed something. Otherwise, the results will become much weaker.\n\n2. Since different items have different contexts, it's more reasonable if the buyer can buy more than one item at the same time. It'll be an interesting extension to consider this scenario.\n\n3. I'm wondering if it's possible to get the logarithmic problem-dependent regret as literature in both dynamic pricing and MAB. Maybe you can do some experiments on this. For example, use regression to find the actual order of $T$ (regress log(Regret) on log(T)).", "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)