Killing the Case for Randomization in Dynamic Assortment Optimization
Pith reviewed 2026-07-02 08:52 UTC · model grok-4.3
The pith
Any locally optimal deterministic policy achieves at least 1/2 minus epsilon of the revenue of the best sampling-based policy in dynamic assortment optimization.
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
Core claim
The authors give a de-randomization procedure that produces a deterministic sequence of assortments from within the support of any sampling-based inventory-agnostic policy while keeping the same expected revenue. A second procedure extends the search beyond the support whenever the underlying static assortment optimization problem can be solved. They prove that every locally optimal deterministic policy, defined as one where replacing any single period's assortment cannot increase total expected revenue, satisfies a performance guarantee of 1/2 minus epsilon relative to the optimal sampling-based policy.
What carries the argument
The de-randomization algorithm that extracts a deterministic sequence of assortments from the support of a sampling distribution over assortments.
If this is right
- Any sampling-based inventory-agnostic policy can be replaced by a deterministic sequence with identical expected revenue.
- When the static assortment problem is tractable, deterministic policies can be found that may exceed the performance of a given sampling-based policy.
- Local search over sequences of assortments produces policies whose performance is within 1/2 - epsilon of the best sampling-based policy.
- Randomization is not required to achieve the performance level of sampling-based methods.
Where Pith is reading between the lines
- The same de-randomization logic could apply to other dynamic stochastic optimization settings that currently rely on sampling to handle uncertainty.
- Practitioners might replace sampling loops with local improvement heuristics over fixed sequences for faster real-time decisions.
- If the epsilon term can be driven to zero under additional structure, the result would imply that the best deterministic policy is essentially as strong as the best randomized one.
- The local-optimality guarantee may connect to constant-factor results in other sequential decision problems where single-swap improvements suffice for approximation.
Load-bearing premise
Dropping products without remaining inventory from an offered assortment does not reduce expected revenue when a customer would have chosen such a product.
What would settle it
An explicit locally optimal deterministic policy whose total expected revenue falls below (1/2 - epsilon) times the revenue of the optimal sampling-based policy under the same choice model and inventory levels.
read the original abstract
One of the traditional approaches for constructing approximate policies for dynamic assortment optimization problems is to use sampling-based inventory-agnostic policies. Such policies are called sampling-based, as they sample an assortment of products from a fixed distribution at each time period to offer to a customer of each type. Such policies are called inventory-agnostic, as the sampled assortments may include products without remaining inventories, so if a customer chooses a product without remaining inventories, then she leaves without a purchase. Inventory-agnostic nature of a policy is not a concern, because it is known that if the policy samples an assortment that includes products without remaining inventories, then dropping the products without remaining inventories does not degrade the performance. However, sampling-based nature of a policy is a concern, because sampling brings another source of uncertainty in the performance. In this paper, we give an algorithm to de-randomize any sampling-based inventory-agnostic policy, so the de-randomized policy offers a deterministic sequence of assortments within the support of the original policy without degrading the performance. Furthermore, we give a variation of our de-randomization algorithm that searches for a deterministic sequence of assortments beyond the support of the original policy. We show that we can implement the latter variation efficiently as long as we can solve the static assortment optimization problem under the choice model governing the choice process of the customers. As our crowning technical contribution, we study locally-optimal deterministic policies, where changing any single one of the assortments in the policy does not improve the total expected revenue. We show that any locally-optimal policy has a performance guarantee of 1/2 - epsilon when compared with the best sampling-based policy.
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The paper claims that sampling-based inventory-agnostic policies for dynamic assortment optimization can be de-randomized into deterministic policies without loss of expected revenue, via an algorithm that outputs a deterministic sequence from the support of the original distribution; a variant efficiently searches outside the support whenever the static assortment problem is solvable. It further claims that any locally optimal deterministic policy (one where no single-period assortment change improves total revenue) achieves a (1/2 − ε) guarantee relative to the best sampling-based policy.
Significance. If the de-randomization and local-optimality claims hold under standard choice models, the result would eliminate the need for randomization in policy construction and reduce the problem to finding locally optimal deterministic sequences, which is conceptually simpler. The (1/2 − ε) guarantee would also provide a concrete performance benchmark for deterministic policies. However, both the de-randomization step and the transfer of the guarantee rest on the unproven background assertion that removing out-of-stock items from an assortment never changes choice probabilities or expected revenue.
major comments (2)
- [Abstract] Abstract: the statement that 'dropping the products without remaining inventories does not degrade the performance' is treated as a background fact rather than derived. This property fails for choice models that renormalize probabilities, incorporate consideration-set effects, or exhibit position bias when an unavailable item is present; if it does not hold, the performance-preserving de-randomization and the subsequent (1/2 − ε) comparison to sampling-based policies both collapse.
- [Abstract] Abstract: the (1/2 − ε) guarantee for locally-optimal deterministic policies is stated without reference to any theorem, proof sketch, or choice-model assumptions under which it is derived. Because the abstract supplies neither the definition of local optimality nor the comparison argument, it is impossible to verify whether the bound is tight or whether it survives the same inventory-agnostic conversion step.
Simulated Author's Rebuttal
We thank the referee for the detailed and insightful comments. We address each major comment below. The concerns highlight the need for explicit assumptions and clearer referencing, which we will incorporate in the revision.
read point-by-point responses
-
Referee: [Abstract] Abstract: the statement that 'dropping the products without remaining inventories does not degrade the performance' is treated as a background fact rather than derived. This property fails for choice models that renormalize probabilities, incorporate consideration-set effects, or exhibit position bias when an unavailable item is present; if it does not hold, the performance-preserving de-randomization and the subsequent (1/2 − ε) comparison to sampling-based policies both collapse.
Authors: We agree that the property is not universal across all conceivable choice models. The manuscript is developed under standard choice models (e.g., MNL and other models without renormalization or position bias) in which the choice probabilities among available products remain unchanged when unavailable items are removed from the assortment. Under these models, the expected revenue is unaffected, which underpins both the de-randomization algorithm and the performance comparison. We will revise the abstract and the relevant sections to explicitly state these choice-model assumptions rather than presenting the property as a background fact. revision: yes
-
Referee: [Abstract] Abstract: the (1/2 − ε) guarantee for locally-optimal deterministic policies is stated without reference to any theorem, proof sketch, or choice-model assumptions under which it is derived. Because the abstract supplies neither the definition of local optimality nor the comparison argument, it is impossible to verify whether the bound is tight or whether it survives the same inventory-agnostic conversion step.
Authors: The (1/2 − ε) guarantee is proven in Theorem 4.3 of the main body, which formally defines local optimality (no single-period assortment change improves total expected revenue) and derives the bound relative to the optimal sampling-based policy under the same choice-model assumptions used throughout the paper. The de-randomization result (Theorems 3.1 and 3.2) ensures that the performance of the sampling-based policy is preserved by the deterministic policy, so the guarantee transfers directly. We will revise the abstract to reference Theorem 4.3, include a concise definition of local optimality, and note the applicable choice models. The paper does not claim the constant is tight; a remark on this can be added if desired. revision: yes
Circularity Check
No circularity; central guarantee derived from local optimality and de-randomization algorithm
full rationale
The paper presents an algorithmic procedure to de-randomize sampling-based inventory-agnostic policies while preserving performance, followed by a variation that searches beyond the original support (efficient when static assortment optimization is solvable). It then defines locally-optimal deterministic policies (no single assortment change improves revenue) and proves they achieve 1/2 - epsilon of the best sampling-based policy. The inventory-agnostic justification is explicitly labeled as external background ('it is known that...'), not derived or fitted inside the paper. No self-definitional reductions, no parameters fitted to data then renamed as predictions, and no load-bearing self-citations appear. The derivation chain is independent of its inputs and relies on new algorithmic construction plus external facts.
Axiom & Free-Parameter Ledger
axioms (1)
- domain assumption Dropping out-of-stock products from sampled assortments does not degrade performance
Reference graph
Works this paper leans on
- [1]
-
[2]
Y. Feng and R. Niazadeh and A. Saberi , title =. Operations Research , volume =
-
[3]
H. Hassani and M. Soltanolkotabi and A. Karbasi , title =. Proceedings of the 31st International Conference on Neural Information Processing Systems , pages =. 2017 , publisher =
work page 2017
-
[4]
Y. Bai and. Coordinated Inventory Stocking and Assortment Customization , journal =
- [5]
-
[6]
N. Golrezaei and H. Nazerzadeh and P. Rusmevichientong. Real-Time Optimization of Personalized Assortments. Management Science. 2014
work page 2014
-
[7]
P. Rusmevichientong and M. Sumida and H. Topaloglu , Title =. Management Science , Year =
- [8]
- [9]
-
[10]
X.-Y. Gong and V. Goyal and G. N. Iyengar and D. Simchi-Levi and R. Udwani and S. Wang , title =. Management Science , volume =
-
[11]
G. Gallego and G. Iyengar and R. Phillips and A. Dubey. Managing Flexible Products on a Network. 2004
work page 2004
- [12]
- [13]
-
[14]
H. Topaloglu , title =. Production and Operations Management , volume =
-
[15]
T. M. V. Vossen and D. Zhang. Reductions of Approximate Linear Programs for Network Revenue Management. Operations Research. 2015
work page 2015
- [16]
-
[17]
J.M. Davis and G. Gallego and H. Topaloglu. Assortment Optimization under Variants of the Nested Logit Model. Operations Research. 2014
work page 2014
-
[18]
J. Blanchet and G. Gallego and V. Goyal. A M arkov Chain Approximation to Choice Modeling. Operations Research. 2016
work page 2016
-
[19]
G. Gallego and R. Ratliff and S. Shebalov. A General Attraction Model and Sales-Based Linear Programming Formulation for Network Revenue Management under Customer Choice. Operations Research. 2015
work page 2015
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.