Motivated by Large Language Model (LLM) cascading, we propose an online contextual Pandora’s Box model for adaptively querying and selecting LLM APIs. In each period, a decision-maker observes a request context and faces a two-phase decision problem. In the query phase, the decision-maker sequentially queries APIs, where each query reveals a generated output and the decision-maker incurs an (output-dependent) cost. In the selection phase, the decision-maker selects one of the generated outputs to deploy and observes only the downstream reward of the deployed output. This output-mediated feedback structure differs from classical online contextual Pandora’s Box models, in which opening a box directly reveals its reward. Rather than estimating the full conditional output and cost distributions of each API, we directly model the reservation index and develop a learning approach for the query phase. Specifically, we impose a parametric structure on the contextual reservation index functions induced by the classical Weitzman’s policy. Our policy combines generalized method of moments (GMM) type estimation of these reservation indices with UCB-style confidence bounds for both these indices and the shared output-level reward evaluator. Under regularity conditions, we prove that the resulting policy achieves dimension-dependent \(\widetilde{O}(\sqrt{T})\) cumulative regret over a horizon of \(T\) periods.

We consider the problem of estimating assortment probabilities, which is common in operations management applications, including product bundling, advertising, etc. Existing approaches typically model each assortment as a category and apply multinomial models to estimate the choice probabilities; while computationally convenient, these methods do not exploit independence structures in the joint distribution and may therefore be statistically inefficient when the total number of items is large. Using the representation from Bahadur (1959), we relate the sparsity of the generalized correlation coefficients to the independence structure of the binary components. We formulate the problem as estimating a high-dimensional vector of generalized correlation coefficients, together with low or moderate-dimensional nuisance parameters corresponding to the marginal probabilities. We develop a regularized adversarial estimator that attains the optimal rate under standard regularity conditions while remaining computationally feasible. The framework naturally extends to settings with covariates. We apply the proposed estimators to causal inference with multiple binary treatments and show substantial finite-sample improvements over non-adaptive methods. Numerical studies corroborate the theoretical results.

We study the estimation of binomial means across a large number of units, particularly in settings where unit-level estimates are noisy because the number of trials is small or the success probabilities are rare. This problem is fundamental in economic applications, including assessing intergenerational mobility of census tracts, estimating prevalence of infectious diseases across countries, and measuring click-through rates for different demographic groups. Existing approaches fall broadly into three categories. The first relies on empirical averages or prediction-based estimators when covariates are available. The second adopts a Bayes or empirical Bayes framework. Current approaches to binomial empirical Bayes largely rely on g-modeling, which identify only a finite set of prior moments and the binomial means are generally only partially identified. The third approximates the binomial observations as Gaussian, imputing their variances using approximations and establishing theoretical guarantees assuming Gaussianity. Such approximations, however, may be less reliable when trial sizes are small or success probabilities are close to zero. Our approach avoids this approximation by working directly with the exact binomial sampling distribution. We formulate the problem as a compound estimation problem, treating the trial sizes, covariates, and mean parameters as fixed, and derive a version of Stein’s Unbiased Risk Estimator (SURE) tailored to squared-error loss for binomial means. This requires a substantially different construction from the classical Gaussian setting, where the corresponding binomial Stein identity does not yield an analogous SURE in a direct form. We therefore derive a more intricate risk estimator that exploits the discrete structure of the binomial distribution. We show that this estimator is exactly unbiased when the candidate estimator is polynomial in the binomial outcome. For general estimators, where exact unbiasedness need not hold, we establish explicit bounds on the resulting bias. We study a general class of Lipschitz estimators and establish slow and fast regret rates under different regularity conditions, along with asymptotic normality and inference for the best-in-class estimator. The class includes linear shrinkage rules that combine the maximum likelihood estimator, the grand mean, and machine learning predictions, as well as Bayes rules under general priors. We demonstrate our approach using three datasets on firm discrimination, education outcomes, and innovation rates, where we find our estimators yield stable performance improvements compared to baseline methods commonly used in existing literature.

Downsampling or under-sampling is a technique that is utilized in the context of large and highly imbalanced classification models. We study optimal downsampling for imbalanced classification using generalized linear models (GLMs). We propose a pseudo maximum likelihood estimator and study its asymptotic normality in the context of increasingly imbalanced populations relative to an increasingly large sample size. We provide theoretical guarantees for the introduced estimator. Additionally, we compute the optimal downsampling rate using a criterion that balances statistical accuracy and computational efficiency. Our numerical experiments, conducted on both synthetic and empirical data, further validate our theoretical results, and demonstrate that the introduced estimator outperforms commonly available alternatives.

Designing learning agents that explore efficiently in a complex environment has been widely recognized as a fundamental challenge in reinforcement learning. While a number of works have demonstrated the effectiveness of techniques based on randomized value functions on a single agent, it remains unclear, from a theoretical point of view, whether injecting randomization can help a society of agents concurrently explore an environment. The theoretical results established in this work tender an affirmative answer to this question. We adapt the concurrent learning framework to randomized least-squares value iteration (RLSVI) with aggregated state representation. We demonstrate polynomial worst-case regret bounds in both finite- and infinite-horizon environments. In both setups the per-agent regret decreases at an optimal rate of Θ(1/√N), highlighting the advantage of concurrent learning. Our algorithm exhibits significantly lower space complexity compared to (Russo, 2019) and (Agrawal et al., 2021). We reduce the space complexity by a factor of K while incurring only a √K increase in the worst-case regret bound, compared to (Agrawal et al., 2021; Russo, 2019). Interestingly, our algorithm improves the worst-case regret bound of (Russo, 2019) by a factor of H^1/2, matching the improvement in (Agrawal et al., 2021). However, this result is achieved through a fundamentally different algorithmic enhancement and proof technique. Additionally, we conduct numerical experiments to demonstrate our theoretical findings.

We consider the concurrent reinforcement learning problem where n agents simultaneously learn to make decisions in the same environment by sharing experience with each other. Existing works in this emerging area have empirically demonstrated that Thompson sampling (TS) based algorithms provide a particularly attractive alternative for inducing cooperation, because each agent can independently sample a belief environment (and compute a corresponding optimal policy) from the joint posterior computed by aggregating all agents' data, which induces diversity in exploration among agents while benefiting shared experience from all agents. However, theoretical guarantees in this area remain under-explored; in particular, no regret bound is known on TS based concurrent RL algorithms. In this paper, we fill in this gap by considering two settings. In the first, we study the simple finite-horizon episodic RL setting, where TS is naturally adapted into the concurrent setup by having each agent sample from the current joint posterior at the beginning of each episode. We establish a Õ(HS√AT/n) per-agent regret bound, where H is the horizon of the episode, S is the number of states, A is the number of actions, T is the number of episodes and n is the number of agents. In the second setting, we consider the infinite-horizon RL problem, where a policy is measured by its long-run average reward. Here, despite not having natural episodic breakpoints, we show that by a doubling-horizon schedule, we can adapt TS to the infinite-horizon concurrent learning setting to achieve a regret bound of Õ(DS√ATn), where D is the standard notion of diameter of the underlying MDP and T is the number of timesteps. Note that in both settings, the per-agent regret decreases at an optimal rate of Θ(1/√n), which manifests the power of cooperation in concurrent RL.