Dynamic Assortment Selection and Pricing with Censored Preference Feedback

We sincerely thank you for taking the time to review our paper and for providing thoughtful and valuable feedback. We greatly appreciate your recognition of our work and your constructive comments. Below, we address each of your comments and questions in detail:

$\bullet$ My main concern is the statement that $1/\kappa =O(K^2)$. Is it true?

Response: Thank you for your question. We confirm that it is indeed correct that $1/\kappa = O(K^2)$ in the worst case. According to our definition in Line 258, $\kappa=\inf\_{t,i,S,p,\theta\in \Theta}P\_{t,\theta}(i|S,p)P\_{t,\theta}(i\_0,S,p)$ where $\Theta=\\{\theta\in \mathbb{R}^{2d}:||\theta^{1:d}||\_2\le 1, ||\theta^{d+1:2d}||\_2\le 1\\}$ and $P\_{t,\theta}(i|S,p)=\frac{\exp(z\_{i,t}(p\_{i})^\top \theta))}{1+\sum\_{j\in S}\exp(z\_{j,i}(p\_j)^\top \theta)}$ (Line 191). Under Assumption 1, we observe that $|z\_{i,t}(p\_i)^\top \theta|\le C$ for constant $C>0$. This implies that, under the constraint $|S|\le K$, $P_{t,\theta}(i|S,p)\ge \exp(-C)/(1+K\exp(C))=\Omega(1/K)$, resulting in $\kappa = \Omega(1/K^2)$ from the definition, which in turn implies $1/\kappa = O(K^2)$. We will add this discussion in our final.

$\bullet$ 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.

Response: Thank you for this suggestion. In our current work, we use the multinomial logit (MNL) model for user choice, where the buyer purchases at most one item at each time step. This single-purchase constraint aligns with many real-world applications where buyers make selective decisions among a set of products presented at once, such as choosing one flight or booking one hotel room.

A multiple-purchase extension could be approached by adapting the choice model to account for the cumulative utility of a subset of items rather than individual item utility alone. Additionally, this scenario could involve modifying the algorithms and regret analysis to reflect multiple decision points per time step. Extending the model to allow multiple purchases per time step would be an interesting direction for future research.

$\bullet$ 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)).

Response: To the best of our knowledge, for contextual bandit problems where the mean reward varies due to dynamic feature information, most existing work emphasizes problem-independent regret, as we do in this paper. This approach is widely used because the changing context leads to arbitrarily varying reward distributions over time, making it challenging to define a stable, problem-dependent regret bound. Given this variability, a worst-case regret bound is a reasonable and robust measure, providing guarantees across diverse and potentially unpredictable scenarios.

$\bullet$ For the TS, you use the maximum of m samples. Then, with high probability, $x^\top\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?

Response: The need for multiple $M$ samples in our Thompson Sampling (TS) approach arises from the requirement to select multiple products for the assortment at each time step. Note that the algorithm is still randomized and selects an assortment based on randomly sampled parameters. While the multiple samples are used to make this set of items a little more optimistic than single sample approach, yet they are far from UCB (that is, an assortment of these items does not form a high-probability optimism as done in UCB) Our TS is still a randomized algorithm, even can be pessimistic at times based on random samples. In contrast, UCB is a deterministic approach where upper confidence bound controls the tradeoff. Thus, there exists the fundamental difference between our TS and UCB algorithms. The nature of our TS algorithm aligns with the linear TS (Abeille & Lazaric, 2017), and prior work on TS for MNL (Oh & Iyengar, 2019) similarly uses multiple samples as we do.

We also highlight that our experimental results demonstrate that TS performs comparably to UCB and sometimes even outperforms UCB when the number of products is sufficiently large (shown in Figure 2 of the revised paper).

Moreover, TS offers computational advantages in assortment selection, especially in high-dimensional settings. Specifically, the computational complexity of the TS-based valuation index for each product, $\tilde{v}\_{i,t} = \arg\max\_{m \in [M]} x\_{i,t}^\top \tilde{\theta}\_{v,t}^{(m)}$, scales as $O(Md) = \tilde{O}(d)$, where $M = O(\log N)$. In contrast, the complexity of the UCB-based valuation index, $\overline{v}\_{i,t} = x_{i,t}^\top \widehat{\theta}\_{v,t} + \beta_\tau ||x\_{i,t}||\_{H\_{v,t}^{-1}}$, scales as $O(d^2)$. This difference makes TS computationally more efficient for calculating an index for valuation (and utility) for assortment selection, particularly when the dimension is large.

We will include this discussion in the final version of the paper.

$\bullet$ 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? ...

Response: We thank the reviewer for their comment and would like to clarify the motivation for including the Thompson Sampling (TS) algorithm in our work. While TS exhibits slightly weaker theoretical regret bounds compared to the UCB-based approach (with an additional $\sqrt{d}$ term, which is consistent with the existing results in other TS algorithms (e.g., Oh & Iyengar, 2019; Agrawal & Goyal, 2013; Abeille & Lazaric, 2017)), our experimental results demonstrate that TS performs comparably to UCB and sometimes even outperforms UCB when the number of products is sufficiently large (shown in Figure 2 of the revised paper).

Moreover, it offers computational advantages in assortment selection, especially in high-dimensional settings. Specifically, the computational complexity of the TS-based valuation index for each product, $\tilde{v}\_{i,t} = \arg\max\_{m \in [M]} x\_{i,t}^\top \tilde{\theta}\_{v,t}^{(m)}$, scales as $O(Md) = \tilde{O}(d)$, where $M = O(\log N)$. In contrast, the complexity of the UCB-based valuation index, $\overline{v}\_{i,t} = x_{i,t}^\top \widehat{\theta}\_{v,t} + \beta_\tau ||x\_{i,t}||\_{H\_{v,t}^{-1}}$, scales as $O(d^2)$. This difference makes TS computationally more efficient for calculating an index for valuation for assortment selection, particularly when the dimension is large. This computational advantage also applies to calculating utility indices.

Both UCB and TS are widely recognized as foundational approaches in bandit literature due to their theoretical and empirical efficiency. UCB represents a deterministic approach, while TS leverages randomized exploration. In our novel problem setting, we have adapted both frameworks to incorporate an integrated pricing strategy and provided rigorous regret analyses for each. Analyzing the regret of TS, in particular, is more challenging than UCB because it requires accounting for estimation errors in the sampled values and establishing optimism properties under the algorithm’s inherent randomness. For these reasons, achieving the regret bound for TS in this context, even after UCB, is widely considered an established contribution in bandit literature (Agrawal & Goyal, 2013; Abeille & Lazaric, 2017). This contribution is particularly significant in our problem setting because extending the analysis from UCB to TS is far less straightforward in our framework. The additional complexities introduced by the integration of pricing strategies and the randomness of TS make this a non-trivial extension, further highlighting the value of our contribution.

Furthermore, as noted in Lines 467–475, this work is the first to apply TS to dynamic pricing under the MNL model, achieving a regret bound without $\kappa$ dependency in the main term and introducing computationally efficient online updates for the estimator. This contribution represents a meaningful step forward for the community, as TS-based algorithms have not been explored in this context before.

For these reasons, we assert that TS is an important contribution to this work. We will include a discussion of these points in the final version of the paper to clarify the motivation and significance of including TS.

We sincerely thank you for taking the time to review our paper and for providing thoughtful and valuable feedback. We greatly appreciate your recognition of our work and your constructive comments. Below, we address each of your comments and questions in detail:

$\bullet$ 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"

Response: Thank you for your feedback. We understand the distinction you are making between proposing a framework and formalizing a new problem. Our intention was to emphasize the structured approach we introduced to address the complexities of dynamic multi-product selection and pricing under preference feedback with censorship (including hidden censorship feedback)—a scenario that closely aligns with real-world applications.

By using the term "novel framework," we aimed to convey the structured model we developed to systematically capture these intricacies, including buyer censorship and dynamic learning of valuations and preferences.

We will adjust the terminology to better reflect this in the revised manuscript.

$\bullet$ 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.

Response: Thank you for this valuable suggestion. We agree that a discussion of regret lower bounds would offer further insight into the complexity of our problem, which involves both price setting and product selection.

We note that previous UCB algorithms for the MNL bandit (without pricing aspect) achieve a regret bound of $d\sqrt{T}$. However, our problem setting extends the MNL bandits to a censored version of MNL integrated with pricing, which introduces additional complexity due to the activation function and hidden censorship feedback. Despite this increased challenge, our approach achieves a regret bound of $d^{3/2}\sqrt{T}$. While we conjecture that the regret lower bound for our problem likely lies between $d\sqrt{T}$ and $d^{3/2}\sqrt{T}$ inclusive, formally establishing this remains an open question.

In our revision, we will include this discussion. We believe this addition will provide readers with a clearer understanding of the difficulty of our problem and the significance of our contributions in achieving this upper bound.

$\bullet$ No experiment on any real-world dataset.

Response: Conducting experiments in bandit settings using offline datasets is inherently challenging due to the nature of partial feedback in online learning. Bandit algorithms rely on feedback that is contingent upon the actions they take, whereas offline datasets typically lack counterfactual feedback—i.e., the outcomes of actions not taken during data collection. This fundamental limitation makes it difficult to directly evaluate bandit algorithms on fixed real-world datasets without significant adjustments.

In most cases, offline datasets must be transformed into semi-synthetic datasets, where missing counterfactual feedback is either imputed or simulated based on assumptions. This transformation effectively reduces real-world data to synthetic, potentially limiting its practical interpretability.

For these reasons, we adopted the approach commonly used in the bandit literature, focusing on theoretical results validated with synthetic datasets. This methodology allows for controlled experimentation and ensures that the theoretical properties of the algorithm are demonstrated under well-defined conditions. However, if the reviewer requests, we are open to performing additional experiments using a semi-synthetic approach with a real-world dataset.

We sincerely thank you for taking the time to review our paper and for providing thoughtful and valuable feedback. We greatly appreciate your recognition of our work and your constructive comments. Below, we address each of your comments and questions in detail:

$\bullet$ Including 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.

Response: We thank the reviewer for their comment and would like to clarify the motivation for including the Thompson Sampling (TS) algorithm in our work. While TS exhibits slightly weaker theoretical regret bounds compared to the UCB-based approach (with an additional $\sqrt{d}$ term, which is consistent with the existing results in other TS algorithms (e.g., Oh & Iyengar, 2019; Agrawal & Goyal, 2013; Abeille & Lazaric, 2017)), our experimental results demonstrate that TS performs comparably to UCB and sometimes even outperforms UCB when the number of products is sufficiently large (shown in Figure 2 of the revised paper).

Moreover, TS offers computational advantages in assortment selection, especially in high-dimensional settings. Specifically, the computational complexity of the TS-based valuation index for each product, $\tilde{v}\_{i,t} = \arg\max\_{m \in [M]} x\_{i,t}^\top \tilde{\theta}\_{v,t}^{(m)}$, scales as $O(Md) = \tilde{O}(d)$, where $M = O(\log N)$. In contrast, the complexity of the UCB-based valuation index, $\overline{v}\_{i,t} = x_{i,t}^\top \widehat{\theta}\_{v,t} + \beta_\tau ||x\_{i,t}||\_{H\_{v,t}^{-1}}$, scales as $O(d^2)$. This difference makes TS computationally more efficient for calculating an index for valuation for assortment selection, particularly when the dimension is large. This computational advantage also applies to calculating utility indices.

Both UCB and TS are widely recognized as foundational approaches in bandit literature due to their theoretical and empirical efficiency. UCB represents a deterministic approach, while TS leverages randomized exploration. In our novel problem setting, we have adapted both frameworks to incorporate an integrated pricing strategy and provided rigorous regret analyses for each. Analyzing the regret of TS, in particular, is more challenging than UCB because it requires accounting for estimation errors in the sampled values and establishing optimism properties under the algorithm’s inherent randomness. For these reasons, achieving the regret bound for TS in this context, even after UCB, is widely considered an established contribution in bandit literature (Agrawal & Goyal, 2013; Abeille & Lazaric, 2017). This contribution is particularly significant in our problem setting because extending the analysis from UCB to TS is far less straightforward in our framework. The additional complexities introduced by the integration of pricing strategies and the randomness of TS make this a non-trivial extension, further highlighting the value of our contribution.

Furthermore, as noted in Lines 467–475, this work is the first to apply TS to dynamic pricing under the MNL model, achieving a regret bound without $\kappa$ dependency in the main term and introducing computationally efficient online updates for the estimator. This contribution represents a meaningful step forward for the community, as TS-based algorithms have not been explored in this context before.

For these reasons, we assert that TS is an important contribution to this work. We will include a discussion of these points in the final version of the paper to clarify the motivation and significance of including TS.

We sincerely thank you for taking the time to review our paper and for providing thoughtful and valuable feedback. We greatly appreciate your recognition of our work and your constructive comments. Below, we address each of your comments and questions in detail:

$\bullet$ The algorithms involve several input parameters, such as $\lambda$, $\eta$, $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.

Response: We provide specific settings for $\eta$ and $\lambda$ in Lines 247 and 424, where we set $\eta = (1/2) \log(K+1) + 3$ and $\lambda = \max\\{84d\eta, 192\sqrt{2}\eta\\}$, which are derived from our regret analysis to ensure effective learning performance. For $C$, we consider any constant $C > 1$, as stated on Line 229. Importantly, $C$ influences the regret bound only by a constant factor of $\sqrt{C}$, which does not hurt the regret in order.

To further clarify the role of each parameter. The parameter of $\eta$ serves as a step size in the online mirror descent updates of $\hat{\theta}_t$ (Line 5 in Algorithm 1), helping to control the convergence behavior in each iteration. The parameter of $\lambda$ is used as a regularization parameter in constructing the Gram matrices $H\_t$ and $H\_{v,t}$ (Lines 2-4 in Algorithm 1). $\lambda$ mitigates variance in the estimation of $\hat{\theta}\_t$, especially under high-dimensional settings, ensuring stability in the updates. The parameter of $C$ impacts the frequency of estimator updates, specifically for $\hat{\theta}\_{v,(\tau)}$ in the LCB pricing strategy (Line 6 in Algorithm 1).

We appreciate this opportunity to elaborate and will incorporate the explanation regarding the parameters in our final version.

$\bullet$ There is no lower bound analysis on the dependency $d$, making it uncertain whether the proposed algorithms are optimal.

Response: Thank you for your feedback. We agree that a discussion of regret lower bounds would offer further insight into the complexity of our problem, which involves both price setting and product selection.

We note that previous UCB algorithms for the MNL bandit (without pricing aspect) achieve a regret bound of $d\sqrt{T}$. However, our problem setting extends the MNL bandits to a censored version of MNL integrated with pricing, which introduces additional complexity due to the activation function and hidden censorship feedback. Despite this increased challenge, our approach achieves a regret bound of $d^{3/2}\sqrt{T}$. While we conjecture that the regret lower bound for our problem likely lies between $d\sqrt{T}$ and $d^{3/2}\sqrt{T}$ inclusive, formally establishing this remains an open question. In our revision, we will include this discussion. We believe this addition will provide readers with a clearer understanding of the difficulty of our problem and the significance of our contributions in achieving this upper bound.

$\bullet$ 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.

Response: To clarify, our approach does not rely on any explicit prior distribution or prior knowledge, consistent with the methodology outlined by Abeille and Lazaric (2016). As they note, “Thompson Sampling can be defined as a generic randomized algorithm constructed on the Regularized Least Squares estimate rather than as an algorithm sampling from a Bayesian posterior.” This principle underpins our implementation of the TS algorithm.

Additionally, our regret analysis adopts a frequentist perspective, ensuring robustness in the worst-case setting without dependence on any assumed prior distribution. This frequentist approach provides regret bounds that are independent of specific priors, making them applicable across a broad range of scenarios.

We will incorporate this discussion in the final version of our paper to prevent any potential misunderstandings about prior knowledge or distributional assumptions.

$\bullet$ 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.

Response: To address this concern, we have expanded the experiments to include larger and more realistic scenarios that better reflect the scale and complexity of practical applications. Specifically, we have conducted additional experiments with the number of products $N=40, 60, 80$ with an increased assortment size $K=5$, and a higher feature dimensionality $d=4$. The results of these experiments are included in Figure 2 in the experiment section of the revised version.