PaperlayerView exact revision on arXiv

Source-linked AI summary

Learning Choice Model Trees for Feature-Based Multi-Product Pricing: Exact Optimization and Field Evidence

Jiajie Zhang, Yanqiu Ruan, Xiao Jin, Chung Piaw Teo

arXiv:2609.16952v1math.OCstat.ML

TL;DR

Feature-based multi-product pricing must capture heterogeneous demand, but greedy choice model trees make split decisions one at a time. OCMT-MNL jointly optimizes a prescribed-depth tree and its MNL leaf models using an exact dynamic program. In a randomized airline experiment, it increased seat revenue per passenger by 11.3% over static pricing.

  • Problem

    Greedy choice model trees select one split at a time, while multi-product pricing requires modeling how customer features shape demand across products.

    Source: §1 · pp. 1–2

  • Method

    OCMT-MNL jointly optimizes feature-based tree splits and leaf MNL models within a prescribed depth using an exact dynamic program.

    Source: §1 · p. 2, §1.1 · p. 3

  • Results

    11.3% higher seat revenue per passenger than the airline’s static pricing baseline in a 23-week randomized experiment.

    Source: §1 · p. 3

  • Takeaways & Limitations

    A fitted tree can support real-time pricing through a leaf-specific one-dimensional lookup table, with revenue loss decreasing quadratically as the grid is refined.

    Source: §1.1 · p. 3

    The formulation assumes every finite leaf problem attains its minimum; compactness of Θ is sufficient.

    Source: §2.1 · p. 7

Abstract

from arXiv · show

Feature-based multi-product pricing uses customer characteristics to identify demand heterogeneity and tailor prices across products. Choice model trees segment customers through interpretable feature rules and fit a demand model within each leaf. Existing methods typically construct these trees greedily, selecting one myopic split at a time. We develop optimal choice model trees with multinomial logit leaves (OCMT-MNL), jointly optimizing the tree and leaf models within a prescribed depth. Our exact dynamic program derives closed-form Fenchel lower bounds during constrained Newton iterations and propagates them across nested and disjoint customer subsets, avoiding new fits and resuming unfinished fits without repeating completed work. In synthetic experiments, it reduces exact leaf fits by 99.98% and leaf evaluations by 86.13%, achieving up to 7.15-fold speedups over unpruned dynamic programming. One-dimensional lookup tables translate offline estimation into real-time pricing, with a revenue-loss bound quadratic in grid spacing under the fitted model. Compared with greedy trees, OCMT-MNL achieves lower revenue loss with fewer leaves on synthetic data and better predictive fit on real data. In a 23-week randomized experiment on ancillary seat pricing across 48 airline markets and 190,220 passengers, OCMT-MNL increases seat revenue per passenger by a statistically significant 11.3% over static pricing.

1 Introduction

Feature-based multi-product pricing must account for heterogeneous demand while keeping segmentation understandable and useful at pricing time. The paper introduces globally optimized choice model trees and evaluates their computational performance, pricing outcomes, and field impact.

1 Introduction

  • Greedy split-by-split construction can lock in early choices, motivating joint optimization of the tree and its leaf choice models within a limited depth.Deeper trees can become harder to understand and audit, so using a prescribed depth effectively matters for interpretable segmentation.Source: §1 · p. 2

1.1 Contributions

  • OCMT-MNL jointly selects feature-based splits and estimates each leaf’s MNL demand model, with an exact algorithm for the global problem.After fitting, a leaf-specific one-dimensional lookup table indexed by a scalar customer score supplies the price vector.Source: §1 · pp. 2–3
  • 11.3% higher seat revenue per passenger than static pricing in a 23-week randomized airline experiment.The experiment covered 190,220 passengers; comparisons with greedy trees also favored OCMT-MNL on synthetic and historical data.Source: §1 · p. 3, §1.1 · p. 3
  • 99.98% fewer exact leaf fits and 86.13% fewer MNL context evaluations yield up to 7.15× speedup over the unpruned dynamic program.The full method combines Fenchel lower bounds during constrained Newton fitting with continuation and cross-set bound propagation.Source: §1.1 · p. 3
  • A leaf’s pricing problem reduces to a scalar fixed point, and lookup-table revenue loss decreases quadratically as the grid is refined.The pricing rule requires tree routing, scalar-index evaluation, and a query to the leaf’s one-dimensional table.Source: §1.1 · p. 3

1.2 Related Literature

  • OCMT-MNL fills a gap between exact tree methods without fitted MNL leaves and choice model trees that retain greedy construction.The paper positions its approach as the first exact method jointly optimizing a prescribed-depth customer segmentation tree and its leaf MNL models.Source: §1.2 · p. 5

1.3 Organization

  • The paper proceeds from model formulation and exact estimation to pricing, computational and model comparisons, field results, and a conclusion.Appendices provide proofs, synthetic data details, historical-data comparisons, and additional field-experiment information.Source: §1.3 · p. 5

2 Model and Problem Formulation

OCMT-MNL represents customer demand with a feature-rule tree whose leaves contain MNL models, then uses the customer’s assigned leaf to formulate a bounded multi-product pricing problem.

2 Model and Problem Formulation

  • The model separates offline estimation of the tree from segment-level pricing after a customer is routed to a leaf.Each leaf’s demand model and resulting price vector are specific to that segment.Source: §2 · pp. 5–6, §2.2 · p. 7

2.1 Choice Model Trees with MNL Leaves

  • Branches use binary indicators directly and numerical features through threshold indicators, keeping the split search finite without enlarging the leaf model.The split candidates are derived from the feature set used in leaf utilities.Source: §2.1 · p. 6
  • The tree partitions the feature space into segments, with maximum depth D, splits from F′, and at least N_min observations per leaf.The number of segments is determined by the tree rather than fixed in advance.Source: §2.1 · p. 6
  • Each leaf has its own MNL parameters, with utility combining a product-specific intercept, a shared feature coefficient, and product-specific price sensitivity.The shared feature coefficient is the structural restriction later used to reduce pricing to a scalar-index problem.Source: §2.1 · pp. 6–7
  • Leaf parameters lie in a shared nonempty closed polyhedron, including a positive lower bound on price sensitivities.The formulation assumes each finite leaf problem attains its minimum; compactness of Θ is sufficient.Source: §2.1 · p. 7

2.2 Segment-Level Pricing

  • For a customer’s assigned leaf, pricing chooses a multi-product price vector to maximize expected revenue under that leaf’s MNL probabilities.The price bounds encode business, regulatory, or experimental restrictions.Source: §2.2 · p. 7

3 Dynamic Programming for Optimal Choice Model Trees

The section develops an exact depth-limited dynamic program for OCMT-MNL, strengthening the search with lower bounds that reuse partial leaf fits and transfer across related customer subsets. It propagates bounds and set relations through recursive cross-set and Bellman updates to obtain an exact root value.

3.3 Branch-and-Bound Pruning

  • The method exposes intermediate constrained-Newton progress to the tree search, enabling bounds to prune leaves before or during fitting while preserving solver work if a leaf remains competitive.If a bound does not prune, fitting continues from the stored solver state rather than repeating completed work.Source: §3 · p. 7, §3.3 · p. 10

3.1 Penalized Estimation Model

  • OCMT-MNL minimizes penalized negative log-likelihood over feasible trees, with each leaf cost a constrained convex MNL estimation problem and a fixed tree’s value equal to the sum of its leaf costs.Because leaves share the feasible parameter set, a fitted parent parameter provides a feasible child warm start without changing the leaf optimum.Source: §3.1 · p. 8

3.2 Exact Bellman Recursion

  • For each customer subset and remaining depth, the Bellman recursion compares stopping at one MNL leaf with the best admissible split and its continuation, yielding an optimal tree over the fixed depth-limited split set.With exact finite leaf costs, Algorithm 1 returns an optimal solution; memoization solves each state once and cached actions recover the tree.Source: §3.2 · p. 9

3.3.1 Fenchel Leaf Bounds

  • A constrained-Newton step supplies a closed-form Fenchel lower bound from the fit’s existing context, direction, and multipliers, avoiding a separate optimization at each checkpoint.Near the optimum on a locally stable active face, the bound gap is of order ν_t^4; when a bound fails to prune, the same path continues without recomputing its context.Source: §3.3.1 · pp. 11–13

3.3.2 Cross-Set Propagation

  • Fenchel bounds transfer to unevaluated target leaves through superset inheritance or aggregation across disjoint subsets, allowing pruning before the target receives its first MNL evaluation.Observation-level additivity preserves source dual values, with the target leaf penalty included once in disjoint-set aggregation.Source: §3.3.2 · p. 14

3.4 The Full Pruned Dynamic Program

  • The full pruned program tests leaf and split actions against an incumbent cap, combining leaf, cross-set, and Bellman bounds to eliminate actions and tighten the cap as exact values return.An unsuccessful leaf test resumes its stored Newton path, while split evaluation recurses under residual caps; later calls under different caps can continue stored work.Source: §3.4 · p. 15
  • The second child is solved under the remaining value after subtracting the first child’s exact value, and the same schedule recurses through the tree.This propagates leaf-level bounds through the full depth of the Bellman recursion.Source: §3.4 · p. 16
  • Induction on remaining depth establishes that the root call with cap +∞ returns the exact value V(D, 0).Each capped call returns either an exact value below its incoming cap or a lower bound reaching that cap.Source: §3.4 · p. 16
  • Increases in direct leaf bounds or newly registered set relations trigger cross-set updates followed by Bellman updates, without adding optimization or Bellman states.Updates operate locally over registered inclusion, binary-union, and parent-state relations.Source: §3.4 · p. 16

4 Optimal Pricing and Online Deployment

With a fitted leaf’s shared feature coefficient, customer-level pricing reduces to a scalar-index problem; lookup tables then support online pricing, with a revenue-loss bound quadratic in grid spacing.

4.1 Within-Leaf Pricing

  • Within a leaf, the shared feature coefficient reduces customer features to a scalar index, and a unique price vector is determined by a scalar fixed point along the clipped-markup path.Customers routed to the same leaf with the same index face the same pricing problem.Source: §4 · p. 16, §4.1 · p. 17

Appendix B.7 proves the fixed-point characterization and the regularity properties in Proposition 4.

  • For correctly specified, locally identified leaves satisfying the moment condition, excess population likelihood loss bounds plug-in pricing loss locally; compact Θ extends the bound globally.Within the local setting, smaller excess likelihood loss gives a tighter upper bound on pricing loss.Source: Appendix B.7 · p. 18

4.2 Online Deployment

  • After offline precomputation, online pricing routes the customer to a leaf, computes its scalar index, and queries the nearest grid point for a price vector.The table is built by solving the fixed-point pricing problem at equally spaced index values.Source: §4.2 · p. 19
  • Halving lookup-grid spacing halves the price-error bound and quarters the revenue-loss bound relative to exact pricing under the same fitted model.The revenue-loss bound remains quadratic in grid spacing even when binding price bounds change.Source: §4.2 · p. 19

5 Synthetic Experiments

The synthetic experiments assess pruning for exact tree estimation and compare globally optimized trees with greedy trees across regimes where local and depth-limited split choices agree to varying degrees. They also evaluate predictive fit on historical airline-market data.

5.1 Experiment Design

  • Synthetic samples contain 5,000 observations and share a five-leaf ground-truth tree; regimes vary whether the locally best root split agrees with the depth-limited optimum.The Conflict regime’s locally preferred d1 split cannot represent right-branch heterogeneity carried by x2 and x3 within the prescribed depth.Source: §5.1 · p. 20

5.2 Efficiency of Pruning

  • Direct reduces MNL context evaluations by 68.4%; Pathwise removes a further 4.4% of remaining contexts by resuming unsuccessful checks.Full’s propagation rules account for 98.5% of pre-fit exclusions.Source: §5.2 · pp. 20–21
  • Across 60 instances, Full reduces exact fits by 99.98%, context evaluations by 86.13%, and computational time by 85.68% versus Pure.At D=4 and B=15, Full takes 311.6 seconds versus 2,227.3 for Pure, a 7.15× speedup.Source: §5.2 · p. 21, Table 1 · p. 21

5.3 Optimal versus Greedy Choice Model Trees

  • In Aligned, OCMT-MNL recovers five leaves with ARI 0.969 versus GCMT-MNL’s 6.2 leaves and ARI 0.858; OOS NLL and revenue loss fall by 1.48 and 0.78 percentage points.The paired 95% intervals for those reductions are [−5.29, 8.25] and [−0.09, 1.64], respectively.Source: §5.3 · p. 22, Table 2 · p. 22
  • In Transition, OCMT-MNL retains the true root and five-leaf structure in every replication, reducing OOS NLL by 12.33 and revenue loss by 1.35 percentage points versus GCMT-MNL.The respective 95% intervals are [0.40, 24.26] and [0.39, 2.32].Source: Table 2 · p. 22, §5.3 · p. 23
  • In Conflict, OCMT-MNL returns the true root and five leaves, with ARI 0.969; its OOS NLL advantage is 22.97 and revenue loss is lower by 1.56 percentage points.GCMT-MNL selects d1 at the root in all 10 replications and grows to 8.6 leaves.Source: Table 2 · p. 22, §5.3 · p. 23
  • Global construction’s advantage grows as the locally attractive split conflicts more with the best depth-limited tree.Likelihood controls revenue loss within a correctly specified leaf, while tree construction determines which observations share that leaf.Source: §5.3 · p. 23
  • On historical data from 48 markets, OCMT-MNL attains lower OOS NLL than GCMT-MNL in 35 markets and a statistically significant average improvement.Source: §5.3 · p. 23

6 Field Experiment in Ancillary Seat Pricing

The field experiment deployed market-specific OCMT-MNL pricing against the airline’s static baseline across 48 OD markets. OCMT-MNL increased revenue per passenger, with gains broadly distributed and concentrated in premium-seat purchases.

6.1 Deployment Setting

  • Deployment used depth-3 models for 48 OD markets, and the fitted trees had a median of five leaves across markets.The depth cap reflects the operational difficulty of maintaining more than eight customer segments.Source: §6.1 · pp. 23–24
  • In the illustrative market, offer stage was the root split, and segment-specific price adjustments reflected demand differences while jointly optimizing across all nine products.Relatively elastic segments generally received discounts, while less-elastic standard-seat demand in two segments received markups.Source: §6.1 · p. 24, Figure 6 · p. 25

6.2 Experimental Design and Estimand

  • The experiment attributed each OD–booking pair’s revenue to its first observed randomized assignment, with the estimand averaged over subsequent independent exposures.The analysis defined RPP as ancillary seat revenue divided by attributed passengers.Source: §6.2 · pp. 24–25

6.3 Revenue Impact

  • 11.3%: OCMT-MNL increased revenue per passenger (RPP) relative to the static baseline, with a 95% bootstrap interval of [1.2%, 22.9%] and a two-sided p-value of 0.027.Figure 7(a) reports the aggregate comparison.Source: §6.3 · p. 25, Figure 7 · p. 26
  • 35 of 48 OD markets had higher RPP under OCMT-MNL, with a median market lift of 25.5%, so the aggregate result was not driven by one large market.Figure 7(b) orders market-level differences by market volume.Source: §6.3 · pp. 25–26, Figure 7 · p. 26

6.4 Revenue Decomposition and Premium-Seat Demand

  • 1.1134 = 1.1074 × 1.0055: most of the RPP ratio was associated with a higher share of positive-revenue bookings, alongside larger premium-seat sales gains than standard-seat gains.Premium seats sold per passenger increased 24.5%, compared with 5.5% for standard groups.Source: §6.4 · p. 26, Figure 8 · p. 27

7 Conclusions

  • Randomization identifies the complete policy’s effect, not effects of individual splits or price changes; the results also rely on MNL-specific properties, including the independence of irrelevant alternatives assumption.Product-specific feature effects would generally make deployment pricing multidimensional, and transfer to richer choice models remains unestablished.Source: §6.4 · p. 26, §7 · p. 27
  • Cross-set propagation of Fenchel bounds and resumable leaf optimization made global tree search practical, reducing exact leaf fits by 99.98% and context evaluations by 86.13%, with speedups up to 7.15×.Global construction jointly allocates shallow-tree splits to retain compact, inspectable trees with demand structure for pricing.Source: §7 · p. 27

A.3 Leaf and Split Evaluation

The appendix describes pathwise leaf evaluation, cross-set bound propagation, and the proof sequence for the estimation and pricing results.

A.3 Leaf and Split Evaluation

  • Pathwise leaf evaluation stores a pending damped step and resumes the constrained Newton fit at its first unevaluated checkpoint.This avoids recomputing an already evaluated MNL context when a leaf check fails.Source: §A.3 · pp. 33–34, §A.4 · p. 35

A.4 Cross-Set Bound Update

  • Cross-set propagation applies Proposition 3 to Bellman-search relations so a propagated bound can prune another leaf before its first context evaluation.A failed leaf check instead advances the exact fit without recomputing a context.Source: §A.4 · pp. 34–35

B Proofs

  • The proofs proceed from the Bellman recursion and Fenchel bounds to their propagation, then establish within-leaf pricing, likelihood-based pricing loss, and lookup approximation.Source: B Proofs · p. 35

B.1 Proof of Theorem 1

These proofs establish global optimality of the Bellman recursion, validate its Fenchel bounds and propagation, and justify the capped recursion’s pruning returns.

B.1 Proof of Theorem 1

  • Memoization solves each subset-and-depth state once, and induction establishes that the root value is globally optimal over the feasible depth-limited trees.The state count grows exponentially in depth if depth grows with the input; the proof notes that depth is typically a small modeler-chosen constant of 3–5.Source: §B.1 · pp. 36–37

B.2 Proof of Lemma 1

  • The Fenchel–Young argument gives a lower bound on a subset’s leaf cost by adding the regularization term to the bound expression.Source: §B.2 · p. 37

B.3 Proof of Proposition 1

  • When the auxiliary probability vectors are componentwise nonnegative, the Fenchel–Young lemma yields the stated leaf-cost lower bound.Source: §B.3 · p. 38

B.4 Proof of Proposition 2

  • The local analysis establishes a fourth-order bound on the constrained gap and convergence of the leaf-bound procedure.The argument uses local face stability and the local quadratic behavior of KL divergence.Source: §B.4 · p. 39

B.5 Proof of Proposition 3

  • For disjoint subsets, Proposition 3’s construction assigns probability vectors observation by observation, allowing the resulting bound contributions to be summed.Source: §B.5 · pp. 39–40

B.6 Correctness of the Bound-Pruned Recursion

  • The capped recursion returns an exact cost below the cap and returns PRUNED only when a valid bound or exact cost reaches it.Checkpoint storage lets a resumed leaf call continue at the first unevaluated step; the root’s infinite cap returns the Bellman value.Source: §B.6 · p. 40

B.7 Proof of Proposition 4

The proof reduces within-leaf pricing to a clipped common-markup path and establishes a unique, stable scalar-index price map.

B.7 Proof of Proposition 4

  • A fixed leaf’s revenue objective depends on customer features only through scalar index s, so equal indices induce the same pricing problem and optimizer.Source: §B.7 · p. 41
  • Every global maximizer lies on a clipped common-markup path, and the pricing problem has a unique optimizer at the fixed point.The proof defines the clipped prices and fixed-point function in the passage.Source: §B.7 · pp. 41–42
  • The unique scalar root and clipped price map are nondecreasing and Lipschitz in the customer index.Source: §B.7 · p. 42

B.8 Proof of Theorem 2

  • The lower-bound argument does not require the two price vectors to have the same active price bounds.Source: §B.8 · pp. 42, 44

B.9 Proof of Proposition 5

The proof bounds price and revenue errors from replacing the exact scalar-index price with its nearest lookup-grid price, including when price bounds change status.

B.9 Proof of Proposition 5

  • The nearest lookup-grid index is within half a grid spacing, and the resulting price deviation is bounded using the scalar price map’s Lipschitz property.Source: §B.9 · pp. 44–45
  • The proof bounds revenue loss with a second-order Taylor expansion in price space, avoiding regime-crossing issues in markup space.The stated revenue-loss bound is quadratic in the grid spacing.Source: §B.9 · pp. 44–46
  • When a product changes between clamped and unclamped status across neighboring grid points, both its marginal-revenue factor and price displacement are O(Δ).If the product remains clamped at the same bound, its price displacement and contribution are zero.Source: §B.9 · p. 45

C Synthetic Data-Generating Process

The synthetic regimes share a common feature set and asymmetric five-leaf ground-truth tree, while differing in leaf parameters. The design tests how tree methods allocate depth across branches and respond to different root-split rankings.

Synthetic regimes

  • The three regimes share the same features, prices, and true tree, and differ only in their leaf parameters.The Aligned transformation makes x1 the best one-step root split while preserving profitable downstream branches; the Transition regime balances one-step preferences between x1 and d1.Source: C Synthetic Data-Generating Process · pp. 46–47

Features and prices

  • Each instance contains 5,000 observations and nine features, including five noise features that do not affect the true segmentation.The continuous features are independently uniform and the binary features independently Bernoulli(0.5).Source: C Synthetic Data-Generating Process · p. 46

True tree structure

  • The ground-truth depth-3 tree has five leaves: the left branch splits on d1, while the right branch splits sequentially on x2 and x3.The root splits on x1 at 0.50; the asymmetry tests whether methods allocate more depth to the more heterogeneous branch.Source: C Synthetic Data-Generating Process · p. 46, Figure 9 · p. 46

MNL parameters

  • Feature coefficients are common across segments and near zero, so within-segment feature effects contribute minimally.Choices are sampled from the segment-specific MNL probabilities, with an outside option of utility zero.Source: C Synthetic Data-Generating Process · p. 47

D Out-of-Sample Comparison in Airline Markets

The airline-market comparison evaluates out-of-sample fit of OCMT-MNL and greedy trees using historical booking data and held-out observations. OCMT-MNL has lower OOS NLL in most markets and the lowest aggregate means among the three methods.

Data and evaluation

  • The comparison uses pre-deployment records from November 2024 through November 2025 across 48 airline OD markets, with nine seat-group products and booking features.A stratified 20% sample within each market is reserved for testing, and all methods use the same features and parameter constraints.Source: D Out-of-Sample Comparison in Airline… · p. 48
  • OCMT-MNL is fitted with depth 3, AIC penalty, and B=8, while GCMT-MNL uses its Section 5.3 growth and validation-pruning settings.The deployed models use the full historical sample; this offline comparison fits on the remaining 80%.Source: D Out-of-Sample Comparison in Airline… · p. 48

Out-of-sample results

E Field-Experiment Sampling and Estimand

The field analysis uses randomly sampled sessions from a platform that independently randomizes policy at each login. Its estimand is the effect associated with the first observed assignment, averaged over subsequent randomized exposure.

Sampling and assignment

  • Each login receives an independently randomized displayed policy, and each session enters the extract with probability 0.10 independently of assignment and outcome.The extract is a random sample of sessions, not a panel containing every login of a sampled booking.Source: E Field-Experiment Sampling and Estimand · p. 49

Estimand

  • Selecting each booking’s earliest sampled login preserves platform randomization conditional on stratum and inclusion, balancing prior unobserved assignments and later reassignments.The comparison identifies the reduced-form effect associated with the policy displayed at that login, averaged over the remaining randomized exposure sequence.Source: E Field-Experiment Sampling and Estimand · p. 49

Scope and inference

  • The estimand is not the effect of persistently assigning one policy throughout a booking or of the unobserved first platform exposure.Reassignment across visits may attenuate contrasts between persistent policy regimes; inference permutes first observed assignments within OD–calendar-week strata and bootstraps bookings stratified by OD and assignment.Source: E Field-Experiment Sampling and Estimand · p. 49

F Learned Segmentations in the Field Experiment

The field experiment’s fitted trees produce compact segmentations, with splits concentrated in days to departure and offer stage. Their leaf models also yield meaningful cross-segment price differentiation, while local elasticities need not track the joint recommended prices.

Tree size and sample size

Selected split variables

  • Days to departure accounts for about 40% of splits, while offer stage accounts for 26% and is the root feature in 27 of 48 trees.Together the two features account for roughly two thirds of splits; their frequencies alone do not identify the behavioral mechanism.Source: F Learned Segmentations in the Field… · p. 50, Figure 11 · p. 50

Leaf models and prescribed prices

  • 98.1% of eligible market–product pairs have negative cross-leaf price-sensitivity versus recommended-price-ratio correlation, and the median cross-leaf recommended-price range is 14.2 percentage points.Among 360 pairs, 88.1% have correlation at most −0.5; 75.5% have a recommended-price range exceeding two percentage points.Source: F Learned Segmentations in the Field… · p. 50
  • Local elasticities at static prices need not vary monotonically with the jointly optimized nine-product prices.For Segment 5, premium products have constant prices across historical observations, so their premium-price spread reflects differences between products rather than request-level price variation.Source: F Learned Segmentations in the Field… · p. 50
Loading 2609.16952v1…