On Pareto Optimality for Parametric Choice Bandits

This paper, "On Pareto Optimality for Parametric Choice Bandits" by Zuo and Qin, addresses a fundamental tension in adaptive experimentation: the trade-off between online performance (minimizing cumulative regret) and post-hoc inferential precision (minimizing the error in estimating revenue contrasts).

Below is a detailed technical summary of the work.

---

1. The Problem: The Regret-Inference Tension

In assortment optimization, a decision-maker selects subsets of items to maximize revenue. Traditional bandit algorithms focus on regret minimization—exploiting high-revenue assortments to maximize cumulative gains. However, such policies often fail to collect sufficient data on suboptimal assortments, leading to "starvation" of information. This makes it difficult to perform reliable post-hoc inference (e.g., comparing the revenue of two different product sets).

The authors formalize this as a multi-objective optimization problem. They seek a "design pair" (an adaptive policy $\pi$ and an estimator $\hat{\Delta}$) that is Pareto optimal, meaning no other design can improve the regret rate without worsening the inference error rate.

2. Methodology: Design-OFU with Predictable Proxies

The authors propose a general framework called Design-OFU (Optimism-in-the-Face-of-Uncertainty). The core technical innovation is the separation of two estimators:

1. Decision Estimator ($\hat{\theta}_t$): A regularized Maximum Likelihood Estimator (MLE) based on all observations, used to drive the sequential decision-making process via an optimistic policy.
2. Inference Estimator ($\hat{e}_{\theta_T}$): A regularized MLE based only on a subset of "forced-exploration" rounds, used to provide unbiased, high-quality estimates of revenue contrasts after the horizon $T$ ends.

Technical Core:

To make this work for general parametric models, they move away from global constants and instead use predictable score and curvature proxies:

• Score Proxies ($\Sigma_t$): Control the concentration of the score function (gradient of the log-likelihood).
• Curvature Proxies ($\Gamma_t$): Control the local shape of the likelihood (Hessian).
  By tracking the realized accumulation of these matrices along the chosen trajectory, they derive a self-normalized concentration inequality and ellipsoidal confidence sets that do not rely on uniform global curvature.

3. Key Contributions

A. General Theory

They establish a unified theoretical framework providing:

• Confidence Sets: Ellipsoidal sets that contain the true parameter $\theta^*$ with high probability.
• Regret Bounds: A bound that explicitly accounts for both the statistical uncertainty and the optimization error ($\epsilon_t$) incurred when the optimistic subproblem is solved approximately.
• Inference Guarantees: Bounds on the error of revenue contrasts derived from the exploration-only estimator.

B. MNL Instantiation and Coverage

The authors apply this framework to the Multinomial Logit (MNL) model. They prove that a balanced spaced singleton-exploration schedule (periodically offering single items) ensures "realized coordinate coverage." This ensures that the information matrix grows at a rate sufficient to provide explicit convergence rates for both regret and inference.

C. Pareto Optimality Analysis

The paper provides a rigorous characterization of the Pareto frontier within the family of polynomial exploration schedules ($n_T \asymp T^\alpha$):

• The Pareto Interval: They prove that $\alpha \in [2/3, 1)$ is the rate-wise Pareto-undominated interval.
• The Balancing Point: $\alpha = 2/3$ is the unique point that minimizes the regret exponent.

4. Key Results

Quantitative Rates (for MNL)

Using an exploration budget $n_T$, the following rates are achieved:

• Regret: $\tilde{O}(n_T + T/\sqrt{n_T})$
• Inference Error: $\tilde{O}(1/\sqrt{n_T})$

When $n_T \asymp T^\alpha$:

• Regret Exponent: $\max\{\alpha, 1 - \alpha/2\}$
• Inference Exponent: $\alpha/2$

The Product Lower Bound

The authors prove a matching lower bound using a "hard two-assortment subclass." They show that for any design, the product of the square root of regret and the inference error is bounded below by a constant:
$$\mathbb{E}[\text{Inference Error}] \cdot \sqrt{1 + \text{Regret}} \geq c$$
This confirms that the trade-off is fundamental and cannot be bypassed.

5. Significance

This paper is significant because it bridges the gap between online learning (bandit theory) and statistical inference (experimental design) in a combinatorial setting.

1. Practical Utility: It provides a blueprint for practitioners to design experiments that are both profitable (low regret) and scientifically useful (reliable inference).
2. Theoretical Robustness: By using curvature proxies rather than global constants, the theory is applicable to a wider range of models (like Exponomial Choice and Nested Logit) beyond the standard MNL.
3. Optimization-Aware: By including $\epsilon_t$ in the regret bound, the theory acknowledges the reality that in large-scale assortment problems, the "optimal" assortment is often found via approximation rather than exact computation.