Online Pandora's Box for Contextual LLM Cascading

Online Pandora's Box for Contextual LLM Cascading

\RUNAUTHOR{Belloni, Chen, and Wei}

\RUNTITLE{Online Pandora's Box for Contextual LLM Cascading}

\TITLE{Online Pandora's Box for Contextual LLM Cascading}

\ARTICLEAUTHORS{ \AUTHOR{Alexandre Belloni} \AFF{The Fuqua School of Business, Duke University, \EMAIL{[email removed]}}

\AUTHOR{Yan Chen} \AFF{The Fuqua School of Business, Duke University, \EMAIL{[email removed]}}

\AUTHOR{Yehua Wei} \AFF{The Fuqua School of Business, Duke University, \EMAIL{[email removed]}} }

\ABSTRACT{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. }

Introduction

The proliferation of Large Language Models (LLMs) has transformed the economics of content generation and decision support. Firms increasingly use generative AI systems to generate advertisements, produce code, serve customer requests, and conduct complex analytical tasks. In these applications, the operational challenge is often not whether content can be generated, but how to generate high-quality content reliably and cost-effectively at scale. A firm that produces a high volume of advertisements per day, for example, may have access to a portfolio of LLM APIs that differ in cost and output quality across task types. More capable proprietary models may, in general, deliver higher-quality outputs but incur substantially higher costs, while smaller or specialized models may be cheaper but less reliable. Because model performance varies across request contexts and it is difficult to predict the quality of the outputs a priori, committing to a single API is often suboptimal. Similarly, querying all of the available APIs is typically prohibitively costly.

We study this problem from the perspective of an organization that uses external or internal LLM APIs to serve a stream of business requests. In such applications, requests arrive as distinct decision units without a strict latency requirement, allowing the decision-maker to query more than one API before selecting a final output. It is worth noting that this request-level decision problem fundamentally differs from the model hosting problem faced by large LLM platforms, where a key operational challenge is to reduce latency through batching, scheduling, and load management yu2022orca,kwon2023efficient,agrawal2024sarathi,ao2025optimizing, jaillet2025online. Our focus is instead on the API consumer's decision problem of dynamically querying a portfolio of APIs to secure high-quality outputs in a cost-effective manner.

A prominent approach for managing this cost-quality trade-off is LLM cascading chenfrugalgpt,yue2024large,gupta2024language. Rather than sending every request directly to a single expensive model, a cascade queries LLM APIs sequentially, typically beginning with lower-cost models and escalating only when earlier outputs appear insufficiently reliable. The pioneering work of chenfrugalgpt, for example, illustrates this design by routing a query through a sequence of LLM APIs and stopping once a generated response receives a sufficiently high reliability score from an evaluator. Cascading allows the easy requests to be handled by cheaper APIs, with only the difficult requests escalated to the expensive ones. Empirical evidence from chenfrugalgpt suggests that such cascades can substantially reduce inference costs while preserving, and in some cases improving, task performance.

The LLM cascading system raises a fundamental sequential decision problem. For each incoming request, the decision-maker must manage both a query phase and a selection phase. In the query phase, the decision-maker must decide which API to query next and whether the generated outputs justify continuing the search. In the selection phase, the decision-maker must decide which of the generated outputs to deploy. These decisions are tightly coupled. Querying another API is costly, but it may reveal a better output; stopping the query phase early saves cost, but significantly increases the risks of not generating a better outcome; and selecting among queried outputs requires evaluating their downstream value. Thus, LLM cascading is not simply a model-routing problem, but a sequential search problem with costly information acquisition.

A natural starting point for principled analysis of this search problem is the classical Pandora’s Box problem. Consider an idealized benchmark in which, for each request, the decision-maker knows the context-dependent distribution of the output-cost pair generated by each API and can evaluate the downstream value of any generated output once it is observed. In this benchmark, querying an API corresponds to opening a box, the inference cost acts as the inspection cost, and the downstream value of the generated output serves as the realized reward. For this formulation, the seminal work of weitzman1979optimal characterizes the structure of the optimal policy. Specifically, given the context of a request, the policy assigns each API a reservation index, then queries APIs in decreasing order of these indices, and terminates the search as soon as the reward of an output exceeds the highest remaining index.

Real applications of LLM cascading, however, depart from this oracle benchmark in ways that make learning central. The value of querying an API is inherently contextual, and the primitives required by the oracle Weitzman's policy are rarely known in advance. In some settings, firms may have substantial historical data on prior human- or AI-generated outputs and their downstream rewards, allowing them to construct an accurate offline model of the reward function. In many others, however, such output-reward pairs are limited or unavailable. Moreover, even when rewards can be modeled from offline data, a firm deploying LLM APIs typically does not know the conditional distribution of outputs and costs generated by each API under a given request context. Since requests arrive sequentially over time, the decision-maker must learn context-dependent reservation indices while continuing to make cost-sensitive query and selection decisions. This naturally leads to an online contextual Pandora’s Box formulation of LLM cascading.

Recent work on LLM cascading has developed increasingly sophisticated methods for balancing cost and performance. Those include budget-constrained cascade policies, uncertainty or threshold-based deferral rules, and hybrid methods that combine cascading with model routing chenfrugalgpt,yue2024large,gupta2024language,zhang2024efficient. While these approaches provide important insights into efficient multi-LLM deployment, they rely primarily on heuristic designs. To the best of our knowledge, existing work has not yet formulated LLM cascading as an online contextual Pandora’s Box problem with joint query and selection, nor developed formal regret guarantees. Conversely, existing Pandora’s Box literature are not directly tailored to this LLM setting. A prominent line of work takes distribution-learning approaches liu2025improved, in which opening a box reveals a scalar reward and the learner estimates how the reward distribution varies with context, under parametric structure on the full distribution. Closer to our work, atsidakou2024contextual parameterizes contextual reservation indices directly, but their model remains a classical Pandora's box setting in which opened boxes reveal rewards directly. In LLM cascading, by contrast, an API call reveals a stochastic output-cost pair. In our model, the downstream value depends on the request and the generated output, while API-specific heterogeneity enters through the distribution of outputs and costs.

Our Contributions

We make three main contributions. First, we introduce an online contextual Pandora's Box model motivated by LLM cascading. Unlike existing online Pandora's Box models, our model features a natural two-phase decision structure: querying an API reveals a stochastic output and incurs a cost, while the downstream reward is observed only after one generated output is selected and deployed. This formulation captures a key practical feature of LLM cascading: API-specific heterogeneity enters through the distributions of generated outputs and costs, while the downstream value of a generated output is evaluated through a shared reward model on the request-output pair. That is, an API can influence the downstream value only through the generated output.

Second, we propose a direct index modeling and learning approach for the query phase. In the full-information benchmark, Weitzman's policy is governed by contextual reservation indices, which are induced by each API's conditional output and cost distributions together with the reward evaluator. Rather than estimating these distributions directly, we impose a parametric structure on the reservation index functions themselves as a generalized linear function of observable context features. This modeling assumption leads to a practical optimism-based learning approach in the LLM cascading setting, as the decision-maker can focus on constructing optimistic box-specific reservation indices from queried output-cost samples through the moment equations instead of the full conditional output distributions. The policy also learns the shared output-level reward evaluator from deployed-output rewards, and the two learned objects jointly determine the cascade's querying and selection decisions.

Third, we provide regret guarantees for the resulting online policy. The policy combines generalized method of moments (GMM) estimation for reservation indices with upper confidence bound (UCB)-style approaches for both the indices and rewards. Our policy is motivated by a simple but crucial regret decomposition under optimism: cumulative regret separates into errors from estimating reservation indices for only the queried APIs and errors from evaluating generated outputs for only the selected APIs. This decomposition allows us to apply the UCB-style analysis to our moment estimation problem, yielding a dimension-dependent $\tilde O(\sqrt{T})$ cumulative regret bound. The analysis covers the practically important known-evaluator regime, where offline data provide an accurate output-level reward model, as well as the full regime where the evaluator and reservation indices must be learned jointly online.

Related Literature

Our work is related to the literature on cost-aware LLM systems, sequential test-time inference, and the theoretical frameworks of sequential search and online learning.

First, our paper is closely related to the emerging literature on LLM cascading and cost-aware multi-LLM deployment. This literature studies how to allocate inference requests across multiple LLM APIs when models differ in cost, latency, and output quality. Representative approaches include FrugalGPT chenfrugalgpt, budget-constrained cascade policies, uncertainty- or reliability-based deferral rules, and hybrid methods that combine cascading with model routing nie2024online,chen2024cascade,zhang2024efficient,yue2024large,gupta2024language. Our work contributes to this literature by formulating LLM cascading as an online contextual Pandora's Box problem, where the decision-maker sequentially decides which APIs to query and when to stop under unknown, context-dependent output and cost distributions. Our work is also related to LLM routing and ensembling methods although they address different decision problems than our LLM cascading motivation. Routing methods usually choose a single LLM for each request before observing any generated output, either through non-predictive rules or through predicted quality, reward, or utility scores hu2024routerbench, shnitzerlarge,hari2023tryage,lu2024routing,vsakota2024fly, mei2025omnirouter. Such methods capture one-shot model choice but not adaptive within-request search. Ensemble methods aggregate or synthesize outputs from multiple LLMs, such as by ranking and fusing candidate responses jiang2023llm,fang2024llm,hu2025efficient; they focus on output aggregation rather than sequential stopping under query costs.

Second, our paper is related to recent work on sequential testing and sequential stopping for LLM inference. huang2026optimal study adaptive self-consistency for a single LLM, where the system sequentially samples reasoning paths and stops once the most-likely answer can be identified with high posterior confidence. li2026asymptotically study Bayesian sequential testing with heterogeneous LLMs, where the decision-maker adaptively chooses which LLM to query and stops once the posterior confidence for a hypothesis crosses a target threshold. These papers formulate LLM inference as posterior-driven sequential testing, whereas our LLM cascading model focuses on contextual sequential search over realized output-cost pairs, with stopping governed by reservation indices and learning focused on both the index functions and the output-level reward model.

Third, the query phase component of our model extends the contextual Pandora’s Box problem. The classic Pandora’s Box problem without contexts originates from the seminal work of weitzman1979optimal and has since been studied under a variety of extensions doval2018whether,chawla2020pandora,fu2020learning,boodaghians2020pandora,agarwal2024semi,ezra2026contract, including online variants gergatsouli2022online,atsidakou2024contextual. In particular, gergatsouli2022online studies an adversarial online Pandora’s Box setting in which box rewards are chosen by an adversary. gatmiry2024bandit subsequently shows that, in this setting, no algorithm can achieve sublinear regret against the optimal policy, even with full-information feedback. For the online contextual Pandora's Box problem, liu2025improved obtains a regret bound of $\widetilde{O}(\sqrt{T})$ for under the assumption that the reward distribution of each box is a location shift of a context-invariant noise distribution, but their results does not apply heterogeneous output distributions across contexts within each box, a key feature for LLM cascading applications. atsidakou2024contextual studies a contextual Pandora's Box model under adversarially arriving contexts, where the optimal reservation index is parametrized as a linear function of the observed context. In this general setting, they obtain an $\widetilde{O}(T^{5/6})$ regret bound by reducing the learning problem to online linear regression. Our approach builds on a similar model of atsidakou2024contextual by imposing a parametric reservation index structure, but adopts a different learning approach through a combination of GMM and UCB analysis. This allows us to propose an optimism-based learning algorithm with $\widetilde{O}(\sqrt{T})$ regret bound under suitable regularity assumptions.

Further, the selection phase of our model draws on the literature on generalized linear contextual bandits. This line of work originates from the seminal paper of filippi2010parametric, which introduces an optimism-based algorithm for generalized linear bandits, and has since been extended in various directions jun2017scalable,kveton2020randomized,ding2021efficient,kim2023double.

Finally, our learning algorithm combines the GMM with an UCB–type algorithm. GMM originates from the seminal work of hansen1982large and has been widely developed and applied in econometrics newey1994large,arellano1991some,chamberlain1987asymptotic,lin2010gmm,cheng2024gmm,andrews2022optimal,hansen2021inference. UCB-type algorithms trace back to the seminal paper of lai1985asymptotically and have since been extensively studied in the bandit literature auer2002finite,rusmevichientong2010linearly,filippi2010parametric,fan2025fragility,garivier2011kl,audibert2009exploration, as well as in broader online learning settings and applications in operations management rakhlin2013optimization,gao2022joint,cheung2022inventory,mao2025model.

In addition, our paper belongs to the growing literature on LLM-assisted decision making across a range of fields, including operations management chen2024large,chen2025manager,simchi2026large, advertising yang2023against,reisenbichler2025applying, healthcare thirunavukarasu2023large,hager2024evaluation,hao2025large, among others.

Notations

Given any integer $k\geq1$ and vector $v\in\mathbb{R}^k$, we use $\|v\|_2$ to denote the Euclidean norm of $v$, and $\|v\|_{\infty}$ to denote $\max_{i=1,\ldots,k}|v_i|$. For any positive semidefinite matrix $\Phi\in\mathbb{R}^{k\times k}$, we use the notation $\|v\|_{\Phi}=\sqrt{v^\top \Phi v}$ to denote the $\Phi$-weighted Euclidean norm of $v$. For matrices $A,B\in\mathbb{R}^{d\times d}$, $A\succeq B$ (resp., $A\preceq B$) means that $A-B$ (resp., $B-A$) is positive semidefinite. For $x,y\in\mathbb{R}$, we write $x\vee y=\max\{x,y\}$. For any positive semidefinite matrix $M\in\mathbb{R}^{d\times d}$, $\lambda_{\min}(M)$ denotes its minimum eigenvalue. For any integer $k\ge1$, let $[k]=\{1,2,\ldots,k\}$. Given any set $S$, we use $S^c$ to denote the complement of $S$. We write $\omega\sim p(\cdot)$ to indicate that the random variable $\omega$ follows distribution $p(\cdot)$. We use $N(\theta,\sigma^2)$ to denote the Gaussian distribution with mean $\theta$ and variance $\sigma^2$. Given any $\mu\in\mathbb{R}^d$ and positive definite matrix $\Sigma\in\mathbb{R}^{d\times d}$, we use $\mathcal{N}(\mu,\Sigma)$ to denote the $d$-dimensional Gaussian distribution with mean $\mu$ and covariance $\Sigma$. For any two random variables $X,Y$, $X\perp\!\!\!\!\perp Y$ means $X$ and $Y$ are independent. For any random event $\mathcal{E}$, we use $\mathbb{I}\{\mathcal{E}\}$ to denote the indicator of $\mathcal{E}$. The notation “a.s.” stands for “almost surely.” For any vector $x$ or matrix $A$, $x^\top$ and $A^\top$ denote their transposes. Finally, for any twice-differentiable function $g$, $g'$ and $g''$ denote its first- and second-order derivatives. We use $\widetilde{O}(\cdot)$ to hide logarithmic factors. Specifically, for functions $f,g:\mathbb{N}\to\mathbb{R}_+$, we write $f(T)=\widetilde{O}(g(T))$ if there exists a constant $C>0$ and a poly-logarithmic function $\mathrm{polylog}(T)$ such that $f(T)\leq Cg(T)\textrm{polylog}(T)$. For random variables $Y_1$ and $Y_2$, $Y_1\lesssim Y_2$ denotes that $Y_1\le cY_2$ with high probability for some constant $c>0$. For two positive sequences $f(T)$ and $g(T)$, we write $f(T)\asymp g(T)$ if both $f(T)\lesssim g(T)$ and $g(T)\lesssim f(T)$ hold up to universal constant factors.

Model

In this section, we formally introduce our online contextual Pandora’s box model motivated by LLM cascading. In our model, there are $A$ different boxes, each of which can be thought of as an API in LLM cascading. There are $T$ decision periods. Let $\mathcal F_{t-1}$ denote the history available before period $t$, including all past observations and actions. At the beginning of period \(t\), the decision-maker (DM) observes a request context vector $x_t \in \mathcal{X} \subset \mathbb{R}^{d_x}$, where $x_t$ are independent across $t\in[T]$. For each box $a \in [A]$, $\omega_{at}$, defined as the potential output vector of $a$, is random and its distribution is assumed to be independent across boxes and independent of the past history. Formally, for each $a\in [A]$, $\omega_{at}$ is drawn from a context-dependent distribution $p_a(\cdot|x_t)$, and for any measurable sets \(B_1,\ldots,B_A\subseteq\Omega\), we have

The output $\omega_{at}$ is revealed only if box $a$ is queried. In addition, if $a$ is queried, a cost $c_a(x_t,\omega_{at})$ is incurred and observed, where \(c_a:\mathcal X\times\Omega\to(0,1)\) is the cost function associated with box $a$. Finally, at the end of each period, the DM selects one queried box $a_{t}$ whose generated output $\omega_{a_{t}t}$ will be deployed. The DM then receives and observes the realized reward associated with the deployed output, $r_{t}=\mu^*(x_t,\omega_{a_{t}t})+\zeta_{t}$, where $\mu^*(\cdot,\cdot):\mathcal{X}\times\Omega\rightarrow[0,1]$ is the (unknown) reward function and $\zeta_{t}$ is the post-deployment noise satisfying $\mathbb{E}[\zeta_t \mid \mathcal{F}_{t-1}, x_t,\omega_{a_t,t}]=0$.

A key feature of our model is that the reward function is shared across boxes. Conditional on the same request-output pair $(x,\omega)$, the expected downstream reward is the same regardless of which box generated the output. Thus, box-specific heterogeneity only enters through the distributions of outputs and costs, while realized rewards depend solely on the common reward function $\mu^*(\cdot,\cdot)$ and noise $\zeta_t$. Consequently, outputs $\omega_{at}$ act as intermediaries linking boxes to rewards, which permits cross-learning of $\mu^*$ using reward observations from all selected boxes. This reflects our motivating LLM example, where the reward received by the DM depends on the generated output and the request it serves, not directly on the identity of the API that generated it.

We preview the parametric structures used for learning, with the formal assumptions and estimators introduced in Sections (ref) and (ref). Suppose, as an oracle benchmark, the DM knows the conditional output distributions \(\{p_a(\cdot\mid x)\}_{a\in[A],x\in\mathcal X}\), the cost functions \(\{c_a\}_{a\in[A]}\), and the reward function \(\mu^*\). Then, after the context $x_t$ is observed, the decision problem in period $t$ reduces to a contextual Pandora's box problem of the type studied by weitzman1979optimal. As we formally illustrate in Section (ref), the optimal full-information policy is determined by two objects: the reward function \(\mu^*\), and the reservation indices, denoted as \(\{\sigma_a^*(x_t)\}_{a\in[A]}\). These indices are, in turn, determined by the oracle objects \(p_a(\cdot|x_t)\), \(\mu^*\), and \(c_a\) through the reservation index equation (ref) in Proposition (ref). In the online learning problem, these oracle objects are not known. Rather than estimating the full conditional output distributions \(p_a(\cdot\mid x)\), we impose generalized linear parametric structure directly on the reward function \(\mu^*\) and on the contextual reservation index functions \(\{\sigma_a^*(\cdot)\}_{a\in[A]}\), namely $\mu^*(x,\omega)=G(\theta_*^\top\phi(x,\omega))$ and $\sigma_a^*(x) = \Lambda(\rho_a^\top\psi(x))$ where the coefficients $\theta_*$ and $\rho_a$ are unknown; $G$, $\Lambda$ are known (monotonic) link functions and $\phi$, $\psi$ are known feature maps, respectively. This allows the DM to learn the shared reward and box specific contextual reservation indices through parametric estimation.

DM's Problem and Regret

Next, we describe the decision-making pipeline in each period $t\in[T]$ in more detail. Each period $t\in[T]$ consists of two phases, which we call query phase and selection phase.

During the query phase, the DM observes $x_t$ and sequentially queries boxes. A policy is non-anticipating: before each query, the DM may use $\mathcal F_{t-1}$, the current context $x_t$, and the output-cost pairs of the boxes already observed in period $t$, but not the output or cost of any unqueried box. Let \(\mathcal A_t\subseteq[A]\) denote the random set of boxes queried in period \(t\). We assume each box can be queried at most once within a period. After each query, the DM observes the generated output and cost, and then decides whether to continue querying or stop. This non-anticipativity condition implies a useful sampling property. For any \(a\in[A]\), conditional on \((\mathcal F_{t-1},x_t)\), the event \(\{a\in\mathcal A_t\}\) is determined before observing box \(a\)'s own potential output-cost pair. Hence, whenever \(\mathbb P(a\in\mathcal A_t\mid \mathcal F_{t-1},x_t)>0\), \[ (\omega_{at},c_{at}) \,|\, \mathcal F_{t-1},x_t,\{a\in\mathcal A_t\} \;\overset{d}{=}\; (\omega_{at},c_{at}) \,|\, \mathcal F_{t-1},x_t. \] This property will be used later to justify learning reservation indices from adaptively queried samples. After the query phase concludes, the DM enters the selection phase, selecting one queried box $a_{t} \in \mathcal{A}_{t}$ whose generated output $\omega_{a_{t}t}$ will be deployed.

Let \(\Pi_t\) denote the class of admissible non-anticipating policies in period \(t\). For a policy \(\pi_t\in\Pi_t\), let \(\mathcal A_t(\pi_t)\) be the set of queried boxes and \(a_t(\pi_t)\in\mathcal A_t(\pi_t)\) be the selected box. The conditional expected utility of policy \(\pi_t\) in period \(t\) is \[ U_t(\pi_t;\mathcal F_{t-1},x_t) := \mathbb E\!\left[ \mu^*(x_t,\omega_{a_t(\pi_t)t}) - \sum_{a\in\mathcal A_t(\pi_t)} c_{at} \,\middle|\, \mathcal F_{t-1},x_t \right]. \] We note that the post-deployment noise $\zeta_t$ does not enter the utility because it is conditionally mean-zero. It matters only as feedback for learning the reward function $\mu^*(\cdot, \cdot)$.

We compare the DM against the full-information benchmark that knows the distribution $p_a(\cdot|x_t)$, and functions $\mu^*(x_t,\cdot), c_a(x_t,\cdot)$ for every box $a$ and every context $x_t$. At each period $t$, after observing $x_t$, the optimal policy $\pi_t^* \in \arg\max_{\pi_t\in\Pi_t} U_t(\pi_t;\mathcal F_{t-1},x_t)$ reduces to the solution of the Pandora's box problem given context $x_t$, which we formally characterize in Section (ref).

Define the condition expected utility of $\pi_t^*$ as \[ U_t(\pi_t^*;\mathcal F_{t-1},x_t) = \mathbb E\bigg[ \max_{a\in\mathcal A_t^*} \mu^*(x_t,\omega_{at}) - \sum_{a\in\mathcal A_t^*} c_{at} \,\bigg|\, \mathcal F_{t-1},x_t \bigg]. \] Then, for any admissible policy \(\boldsymbol \pi=\{\pi_t\}_{t\in[T]}\), the cumulative regret is defined as \[ R_T(\boldsymbol \pi) := \sum_{t=1}^T \mathbb E\!\left[ U_t(\pi_t^*;\mathcal F_{t-1},x_t) - U_t(\pi_t;\mathcal F_{t-1},x_t) \right]. \]

Readers familiar with the bandit literature might ask whether the problem can be modeled as a contextual bandit by treating each API as an arm. Such a formulation would lead to a one-shot API-as-arm policy, in which the decision-maker selects a single API for each request before observing any generated output. It does not, however, capture the adaptive information-acquisition structure of LLM cascading. The following example illustrates that such a restriction can create a constant per-period gap relative to the sequential-search benchmark, even when all primitives are known.

Consider an example with two boxes and the context $x_t$ is fixed throughout. Querying box 1 costs \(c_1=0.5\) and always generates output \(\omega_{1t}=1\). Querying box 2 costs \(c_2=0.01\) and generates output \(\omega_{2t}=1\) with probability \(0.1\), and \(\omega_{2t}=0\) otherwise. The downstream value is \(\mu^*(x_t,\omega)=\omega\). A one-shot API-as-arm policy obtains expected utility $0.5$ from box 1 and \(0.09\) from box 2, so the best one-shot policy selects box 1. Now consider a cascade that first queries box 2. If \(\omega_{2t}=1\), it stops and selects box 2; if \(\omega_{2t}=0\), it queries box 1 and selects box 1. Its expected utility is $-0.01 + 0.1 + 0.9(0.5) = 0.54 > 0.5$. Thus, relative to the cascade benchmark, any one-shot API-as-arm formulation suffers a constant per-period optimality gap in this instance, and hence a loss that grows linearly with \(T\).

Policy and Algorithm

This section develops the online policy and the algorithm. We begin with the full-information benchmark. Fix a period $t$ and condition on the arriving context $x_t$. Suppose the DM knows the reward function $\mu^*(\cdot,\cdot)$ and the output distributions $\{p_a(\cdot|x)\}_{a\in[A],x\in\mathcal{X}}$. The following proposition characterizes the optimal oracle policy during period $t$.

Define $\sigma_{at}^*:=\sigma_a^*(x_t)$. When the costs ${c_{at}}$ are known constants (i.e., $c_{at} \equiv c_a$ for each $a \in [A]$), the indices $\{\sigma_{at}^*\}_{a\in[A]}$ are optimal by the seminal work of weitzman1979optimal. When costs are stochastic (as in our motivating setting), the result above follows from a minor adaptation of the proof in kleinberg2016descending (see Appendix (ref)).

Proposition (ref) formally identifies the reward evaluator $\mu^*(x,\omega)$ and the reservation index function $\sigma_a^*(x)$ as the two objects required to make the optimal sequential decisions. We next describe the online policy as Algorithm (ref). At a high level, the policy follows the oracle structure in Proposition (ref), but replaces the unknown reward evaluator and reservation indices with optimistic estimates. We call the resulting policy COst-aware Sequential MOdel query and Selection, or COSMOS\ .

Optimism and Regret Decomposition

Our COSMOS\ policy constructs optimistic estimates $\widetilde \mu_t(x,\omega)$ and $\widetilde \sigma_{at},\ \forall a\in[A], t\in[T]$. The estimate $\widetilde \mu_t(x,\omega)$ is an optimistic estimate of $\mu^*(x,\omega)$ for a realized output. The estimate $\widetilde \sigma_{at}$ is an optimistic estimate of the oracle reservation index $\sigma_a^*(x_t)$ for box $a$ at the current context. The formal construction of these estimates is postponed to Sections (ref) and (ref), and here we focus only on their roles in the policy.

To understand why optimism is crucial in our COSMOS policy, we next present a theorem showing that, under optimism, the one-period regret decomposes into the reward estimation error for the selected output and the index estimation errors for the queried boxes.

We provide intuition on why Theorem (ref) holds. Consider an auxiliary “optimistic” problem in which both its reward estimate $\widetilde\mu_t$ and its index $\widetilde\sigma_{at}$ upper-bound the truth. Then COSMOS\ is the optimal policy for the “optimistic” problem, and its corresponding optimistic expected value is thus at least as large as the optimal expected value of the true problem. As a result, the loss can be bounded by the discrepancy between the optimistic quantities used by COSMOS\ and the true quantities realized along the same path. This yields exactly two errors: a reward estimation error for the selected output, and an index-estimation error for every queried box.

The decomposition in Theorem (ref) allows us to leverage the principle of optimism to control our regret. More specifically, if a box is queried frequently, its query dataset grows and its index uncertainty decreases. If a box is queried rarely, then it contributes only rarely to the second term in Theorem (ref). This mirrors the classic self-correcting principle behind UCB analysis, adapted here to govern reservation indices and reward rather than the direct feedback in bandits.

Consequently, Theorem (ref) motivates us to construct high-probability confidence bounds for both reward and reservation indices and using them to define the optimistic estimators $\widetilde{\mu}_t(x_t,\omega_{at})$ and $\widetilde{\sigma}_{at}$. The goal is to ensure that, with high probability, these estimators upper bound their population counterparts while remaining sufficiently accurate. Together, optimism and error control provide the key ingredients for deriving the final regret guarantee of the COSMOS\ policy, whose high-level structure is summarized as Algorithm (ref). The full implementation, including the computation of optimistic reservation indices and reward estimates, is deferred to Algorithm (ref) in the Appendix.

Results under Known Reward Function

To build intuition, we first study the case in which the reward function $\mu^*(x,\omega)$ is known. This setting is practically relevant when the reward model can be estimated offline using a substantially larger historical dataset. If the offline data are sufficiently rich, the resulting estimate of reward function $\mu^*(\cdot,\cdot)$ may be accurate enough relative to the $\sqrt{T}$ scale of the online regret analysis, to be treated as fixed in the subsequent online decision problem. Importantly, even with a known reward function, the conditional distribution of the output $\omega_{at}$ given $x_t$ typically remains unknown.

This case therefore captures regimes in which the main online learning challenge is not reward estimation, but learning the reservation indices and managing exploration across boxes. Indeed, once box $a$ is opened in period $t$, the decision-maker observes its output $\omega_{at}$ and cost $c_{at}$, and can therefore compute the conditional expected reward $\mu^*(x_t,\omega_{at})$. Thus, in Algorithm (ref), we would set $\widetilde{\mu}_t(x_t,\omega_{at})=\mu^*(x_t,\omega_{at}).$ The selection rule then chooses the opened box with the largest true conditional expected reward, and the regret component arising from reward estimation disappears. The remaining learning problem is then focused solely on estimating $\sigma_a^*(x_t)$ for each $a$.

This is analogous to the bandit-feedback setting in atsidakou2024contextual, in that feedback is obtained only from opened boxes.\footnote{The authors also study a full information setting where the DM observes the rewards of all boxes at the end of each round.} atsidakou2024contextual develop a black-box reduction from contextual Pandora's Box to online regression, using a specially designed linear-quadratic loss to learn all the reservation indices. In contrast, our approach follows the principle of optimism from the UCB literature. As we illustrate, under suitable regularity conditions, it is not necessary to learn all boxes' index functions uniformly well. Instead, it is enough to maintain optimistic index estimates and refine the estimates of boxes that remain relevant to the query process.

We next formalize this intuition. Recall from Section (ref) that we impose the parametric structure on the indices

where $\Lambda$ is a known monotonic link function, and $\psi(\cdot)$ is a known feature map. We impose the following regularity condition on the parametric reservation index function (ref):

The range restriction $\Lambda:\mathbb{R}\to[-1,1]$ is consistent with the fact that $c_{at}\in(0,1)$ and $\mu^*\in[0,1]$, which imply $\sigma_{at}^*\in[-1,1]$. In addition, Assumption (ref) imposes only mild regularity conditions. It accommodates the linear reservation index specification considered by atsidakou2024contextual, which corresponds to taking $\Lambda$ as the identity map on the relevant, strictly bounded domain of $\rho^\top\psi(x)$, while allowing it to smoothly flatten to $\pm1$ as $s\to\pm\infty$.

Assumption (ref) yields the point identification of $\rho_a^\top\psi(x_t)$:

At the beginning of period $t$, Algorithm (ref) estimates $\rho_a$ by $\hat{\rho}_{at}$ and constructs an upper confidence bound for the linear index $\rho_a^\top\psi(x_t)$. Let $\mathcal{R}_{at}(x_t)$ denote the corresponding confidence radius, and define $\widetilde{\sigma}_{at} = \Lambda\!\left( \hat{\rho}_{at}^{\top}\psi(x_t) + \mathcal{R}_{at}(x_t) \right)$. Let $\mathcal{E}_{\rho}$ denote the high-probability event on which \[ \left| \hat{\rho}_{at}^{\top}\psi(x_t) - \rho_a^\top\psi(x_t) \right| \leq \mathcal{R}_{at}(x_t), \qquad \forall a\in[A],\; t\in[T]. \] Then on $\mathcal{E}_{\rho}$, by the monotonicity of $\Lambda$, \[ \widetilde{\sigma}_{at} \geq \Lambda(\rho_a^\top\psi(x_t)) = \sigma_{at}^*, \qquad \forall a\in[A],\; t\in[T], \] allowing us to invoke the regret decomposition of Theorem (ref). Recall that $\widetilde{\mu}_t=\mu^*$ in the known-$\mu^*$ case, implying the reward estimation term in Theorem (ref) is zero. Therefore, under the event $\mathcal{E}_{\rho}$, Theorem (ref) implies that the period-$t$ regret satisfies

where $\mathcal{A}_t$ is the random set of boxes opened by Algorithm (ref) in period $t$. Inequality (ref) illustrates that the regret depends only on the index estimation errors of boxes that are actually opened. Thus, frequently opened boxes yield larger sample sizes that shrink their confidence radii, while rarely opened boxes contribute negligibly to the overall regret. Once we obtain a valid high-probability confidence radius for the linear index $\rho_a^\top\psi(x_t)$, the cumulative regret can be controlled by the standard elliptical-potential argument used for contextual bandits abbasi2011improved. However, unlike in standard contextual bandits, an opened box does not produce a noisy observation of its reservation index $\sigma_{at}^*$; but instead, a tuple $(x_t,\omega_{at},c_{at})$. Therefore, the index parameter must be learned indirectly from the defining equation (ref) of the reservation index.

Index Estimation and Loss Function

We next describe how to estimate the box-specific reservation index function $\sigma_a^*(\cdot)$. Given (ref) and (ref), our estimation problem is moment-based and is thus inspired by the generalized method of moments (GMM). For this purpose, we define the known-$\mu^*$ moment function, for any $x\in\mathcal{X}$, $\omega\in\Omega$, $c\in[0,1]$, and $\rho\in\mathcal{B}$, as

By Equation (ref), we have $ \mathbb{E}\left[ m^*(x_t,\omega_{at},c_{at};\rho_a) \,\bigg|\, \mathcal{F}_{t-1},x_t,\ a\in\mathcal{A}_t \right] =0$. Next, let \[ \mathcal{S}_{at}:=\{s<t:\ a\in\mathcal{A}_s\}, \qquad n_{at}:=|\mathcal{S}_{at}| \] denote the set and number of past periods in which box $a$ was queried before period $t$, and the elements in $\mathcal{S}_{at}$ be ordered as $\tau_{a,1}<\tau_{a,2}<\cdots<\tau_{a,n_{at}}.$

As we discuss below, our estimation problem is a special case of the GMM framework with conditional moment conditions. By setting the moment conditions based on the features $\psi(x_s)$, we can formulate it as a $M$-estimation problem that is more suitable for our online learning setting. A standard GMM approach would instead form the empirical vector moment \[ \bar g_{at}(\rho) := \frac{1}{n_{at}} \sum_{s\in\mathcal{S}_{at}} \psi(x_s)m^*(x_s,\omega_{as},c_{as};\rho) \] and minimize a quadratic criterion such as $\bar g_{at}(\rho)^\top W_{at}\bar g_{at}(\rho)$ for some positive definite weighting matrix $W_{at}$ at each period $t$. However, this approach focuses on estimating the coefficients $\rho_a$, which requires a full-rank condition on the local GMM curvature. Such a requirement can be overly stringent in our setting, as it requires that the observations in which box $a$ is queried contain sufficiently many “active” samples, namely those satisfying $\mu^*(x_t,\omega_{at})>\Lambda(\rho_a^\top\psi(x_t))$, and that the corresponding feature vectors $\psi(x_t)$ span the parameter space in a well-conditioned way conditional on $a\in\mathcal{A}_t$.

Our objective, however, is not to recover the entire vector $\rho_a$. For the UCB analysis, it is enough to construct a confidence interval for the scalar quantity $\rho_a^\top\psi(x_t)$ at the current context. We therefore adopt an $M$-estimation formulation, whose first-order condition recovers the sample moment.

For a queried sample of box $a$ in period $s$, define

Note that $\ell_{as}(\rho)$ is convex in $\rho$, as $\Lambda(\cdot)$ is strictly increasing. Also, the derivative of $\ell_{as}$ satisfies

Therefore, the first-order condition of the empirical loss minimization is equivalent to the sample analogue of the vector moment equation. The known-$\mu^*$ estimator of $\rho_a$ for period $t$ is

We next state the regularity condition that yields curvature of the population loss. The condition requires that $\rho^\top\psi(x)$ remains in a bounded region, and for every point in this region, there is some probability mass that the reward of the output is above its corresponding reservation index.

Assumption (ref) rules out the cases in which the reservation index lies in a region with no probability mass above it. Together with the lower derivative bound $\Lambda'(\cdot)\geq \mu_1$ from Assumption (ref), it ensures that the reservation index moment crosses zero with slope bounded away from zero. This is the one-dimensional source of curvature for the loss function.

The curvature bound in Lemma (ref) illustrates the advantage for using the $M$-estimation formulation. It shows that the population loss increases quadratically in the prediction error $\psi(x_s)^\top(\rho-\rho_a)$. As a preview of the subsequent analysis, we will compare this quadratic curvature against the empirical fluctuation of the additive loss $\sum_{s\in\mathcal{S}_{at}}\ell_{as}(\rho)$. By controlling this fluctuation uniformly over $\rho\in\mathcal{B}$ via martingale concentration, we can absorb it into the curvature term. This procedure yields a high-probability bound on $|(\hat{\rho}_{at}-\rho_a)^\top\psi(x_t)|$, providing the confidence radius needed to construct the optimistic index $\widetilde{\sigma}_{at}$ in (ref).

Confidence Bound for a Fixed Box

Next, we construct confidence radii for the reservation indices. For each fixed box $a \in [A]$, because $\Lambda(\cdot)$ is monotone and $\sigma_{at}^*=\Lambda(\rho_a^\top\psi(x_t))$, we focus on constructing a confidence interval for the scalar index $\rho_a^\top\psi(x_t)$ at the realized context $x_t$. We define $H_{at}(\rho)$, the empirical fluctuation of the loss at $\rho$, as

By optimality of $\hat{\rho}_{at}$, the empirical excess loss $\sum_{s\in\mathcal S_{at}} \left\{\ell_{as}(\hat{\rho}_{at}) - \ell_{as}(\rho_a) \right\}$ is non-positive. This sum can be decomposed by its conditional expectation and empirical fluctuation as $$ \sum_{s\in\mathcal S_{at}} \left\{\ell_{as}(\hat{\rho}_{at})-\ell_{as}(\rho_a)\right\} = \sum_{s\in\mathcal S_{at}} \mathbb E\left[\ell_{as}(\hat{\rho}_{at})-\ell_{as}(\rho_a) \,\middle|\, \mathcal F_{s-1},x_s \right]+ H_{at}(\hat{\rho}_{at}). $$ Lemma (ref) implies that the conditional expectation is bounded below by the quadratic form $\kappa\mu_1/2 \sum_{s\in\mathcal S_{at}} \left\{\psi(x_s)^\top(\hat{\rho}_{at}-\rho_a)\right\}^2$. Consequently, to establish a confidence interval for $\rho_a^\top \psi(x_t)$, it suffices to bound the empirical fluctuation $H_{at}(\hat{\rho}_{at})$ using a comparable quadratic term and a logarithmic complexity term, as established in the following lemma.

Lemma (ref) is derived through standard concentration arguments. For a fixed $\rho$, $H_{at}(\rho)$ form a martingale difference sequence whose conditional variance is controlled by the quadratic term that appears in the population curvature lemma. A peeling argument over the size of this quadratic term and an $\epsilon$-net argument over $\mathcal B$ yield the uniform bound and hence for adaptive $\rho_t$.

We now build the confidence interval for the scalar index $\rho_a^\top\psi(x_t)$ using Lemmas (ref) and (ref). Define the regularized empirical design matrix

where $\eta_1>0$ is a regularization parameter and $\mathbf{I}_m$ is the \(m\times m\) identity matrix. Intuitively, $V_{at}(\eta_1)$ summarizes the contexts in which box $a$ has been queried before period $t$. The next proposition establishes a high-probability bound on $|(\hat{\rho}_{at}-\rho_a)^\top \psi(x_t)|$.

Proposition (ref) has the usual online-learning interpretation abbasi2011improved,lattimore2020bandit as the confidence bounds used in bandit UCB algorithms. It is large when the current context points in a direction that has not been well explored for box $a$, and small when the historical opened-box contexts provide enough information in that direction.

Motivated by Proposition (ref), we define the optimistic index in the known-$\mu^*$ case as

Since $\Lambda$ is increasing, Proposition (ref) implies $\widetilde{\sigma}_{at}\geq \sigma_{at}^*$ uniformly over $a\in[A], t\in[T]$ with probability at least $1-\delta$. This, in turn, is used to establish the uniform optimism event required for the regret guarantee. In implementation, one may calibrate this radius using a bootstrap approximation to the distribution of $(\hat{\rho}_{at}-\rho_a)^\top\psi(x_t)$, which may yield less conservative confidence bounds. Such a bootstrap procedure is not covered by the present theory and proving its validity would require a uniform bootstrap approximation under adaptive sampling.

Regret under Known Reward Function

Now we bound the cumulative regret when $\mu^*$ is known so that $\widetilde{\mu}_t=\mu^*$. When the indices are optimistic, i.e., $\widetilde{\sigma}_{at}\geq\sigma_{at}^*, \forall a\in[A],\ t\in[T]$, Theorem (ref) gives $\Delta_t(\tilde{\pi}) \leq \mathbb{E}\left[ \sum_{a\in\mathcal{A}_t} \left(\widetilde{\sigma}_{at}-\sigma_{at}^*\right) \,\middle|\, x_t,\mathcal{F}_{t-1} \right]$. Using the Lipschitz continuity of $\Lambda$ and the confidence bound in Proposition (ref), we obtain $\widetilde{\sigma}_{at}-\sigma_{at}^*\leq2LB_{at}^*\|\psi(x_t)\|_{V_{at}(\eta_1)^{-1}}$ on the high-probability event, where $B_{at}^*\leq\mathrm{O}(\sqrt{m\log(T)+\log(TA)})$. Thus the cumulative regret is controlled by $\sum_{t=1}^T\sum_{a\in\mathcal{A}_t}\|\psi(x_t)\|_{V_{at}(\eta_1)^{-1}}$. Every time box $a$ is queried, the corresponding feature vector $\psi(x_t)$ is added to its design matrix. Therefore, the uncertainty in the same direction decreases over time. The standard elliptical-potential argument implies that for each box $a\in[A]$,

Summing this bound over the $A$ boxes yields the following regret guarantee:

Compared with the $\widetilde O(T^{5/6})$ bound of atsidakou2024contextual for a more general contextual Pandora’s Box setting, our $\widetilde O(\sqrt T)$ rate relies on the additional local-curvature structure in Assumption (ref), which enables UCB-style confidence control for the reservation indices.

Results under Unknown Reward Function

We now drop the assumption that $\mu^*$ is known and study the problem where $\mu^*$ must be learned online. The known-$\mu^*$ result before guides the analysis when $\mu^*$ is unknown. Relative to the previous section, two additional challenges arise:

Recall from Section (ref) that we impose the generalized linear parametric structure on the expected reward function:

where $G:\mathbb{R}\rightarrow[0,1]$ is strictly increasing. In Section (ref) we address (i) using a standard penalized maximum likelihood estimator (MLE) construction based on (ref). In Section (ref) we address (ii) by showing that the main intuitions from Proposition (ref) continue to work. Particularly, Proposition (ref) extends Proposition (ref) to this setting by accounting for the plug-in error for the loss. Similarly, the index estimator is controlled by population curvature, empirical concentration, and now an additional perturbation term from reward estimation. Once the reward parameter is learned at the standard online rate, this perturbation is small enough to preserve the overall $\widetilde O(\sqrt T)$ regret rate.

However, challenge (ii) with unknown reward is more delicate because reward learning uses selected outputs while index estimation is based on queried outputs. Hence controlling the plug-in loss requires an additional assumption ensuring that the reward-design matrix is sufficiently informative for the queried features that enter the index estimator.

We begin by imposing the following regularity condition on the expected reward function:

Assumption (ref) is standard in the generalized linear contextual bandit literature filippi2010parametric,li2017provably,lee2024unified. The Lipschitz constant $L$ controls how errors in $\hat\theta_{t-1}$ propagate into the reward prediction, the lower bound $\underline\mu$ on $G'$ ensures uniform strong convexity of the objective, and the boundedness of $\phi$ and $\theta_*$ keeps the analysis in the standard regime.

We next assume that the random reward observed by the DM is drawn from a canonical exponential family:

Assumption (ref) is standard in generalized linear contextual bandit filippi2010parametric,li2017provably,zhou2019learning,lee2024unified, which encompasses Bernoulli, logistic, and binomial reward distributions, and more generally the exponential family (e.g. Gaussian, Poisson, etc.) with support truncated to $[0,\gamma_{0}]$. By definition, taking derivative of $b$ we get $b'=G$ as the inverse link function. Common examples of $G$ include any known cumulative distribution function (CDF) such as the logistic and probit CDFs.

Estimating the Reward Parameter

The reward estimation follows essentially a generalized linear contextual bandit framework. At each period $t$ the deployment $(x_t,\omega_{a_tt})$ yields a reward observation $r_t$, and the dataset $\{(x_k,\omega_{a_kk},r_k)\}_{k=1}^{t-1}$ accumulates over time. We estimate $\theta_*$ by a penalized (projected) maximum likelihood estimator

where

is the regularized design matrix of reward features collected through period $t-1$, and $\eta_0>0$ is a regularization parameter, $\mathbf{I}_d$ is the \(d\times d\) identity matrix. The term within the weighted norm $\|\,\cdot\,\|_{\Phi_{t-1}^{-1}}$ in (ref) is the gradient of the objective function for the unconstrained penalized log-likelihood $\max_\theta\sum_{k=1}^{t-1}\log f(r_k\mid x_k,\omega_{a_kk})-\tfrac{\eta_0}{2}\|\theta\|_2^2$, and $\hat{\theta}_{t-1}$ can be viewed a “projection” onto $\Theta$ if the unconstrained solution falls outside $\Theta$. This construction follows filippi2010parametric.

The following standard result provides a high-probability bound on the prediction error induced by using $\hat{\theta}_{t-1}$ to evaluate the reward of a candidate context-output pair $(x_t,\omega_{at})$.

This is the ellipsoidal confidence bound for generalized linear bandits, which has similar structure as Proposition (ref) for the index parameter estimation error bound. The matrix $\Phi_{t-1}$ plays the role that $V_{at}(\eta_1)$ played for the indices, and $\beta_t$ grows logarithmically in $t$. The proof of Lemma (ref) adapts filippi2010parametric via a self-normalized martingale inequality. Equipped with this bound, we construct the optimistic reward as

Because $G$ is monotonically increasing by Assumption (ref), Lemma (ref) implies that with probability at least $1-\delta/2$, uniformly over all $a\in[A]$ and $t\geq 2$, $\widetilde{\mu}_t(x_t,\omega_{at})\;\geq\;\mu^*(x_t,\omega_{at})$.

Estimating Indices

Next, we estimate the reservation indices and construct their associated confidence intervals for the regime where the reward function is unknown. As an unknown-reward analogue to Section (ref), we replace the true reward $\mu^*(x_s,\omega_{as})$ by its plug-in estimate $G(\hat\theta_{t-1}^\top\phi(x_s,\omega_{as}))$ for each $s \leq t$. The main goal is to show that this substitution preserves the same confidence-bound structure as Proposition (ref), up to an additional perturbation term controlled by the reward estimation error bound. Fix a period $t$ and a box $a\in[A]$. For any $\rho\in\mathcal B$ and any past queried sample $s\in\mathcal S_{at}$, define the plug-in loss

This is the same loss as (ref), with $\mu^*$ replaced by the current reward estimate. The plug-in index estimator is

The first-order condition of (ref) is the empirical analogue of the Weitzman moment equation with the reward function evaluated at $\hat\theta_{t-1}$. The new challenge compared to Section (ref) is that the empirical loss in (ref) is not the oracle loss. To isolate this difference, define the plug-in perturbation

where $\ell_{as}(\rho)$ is the known-$\mu^*$ loss in (ref). The term $J_{at}(\rho)$ measures how the estimation error of $\hat\theta_{t-1}$ propagates into the index-estimation loss.

We impose the following additional assumption for the unknown-reward case. It ensures that the reward-design matrix contains enough information in all directions needed to control the plug-in perturbation. We use $\mathrm{polylog}(T)$ to denote a quantity bounded by a polynomial in $\log T$ (i.e. $\mathrm{polylog}(T) = \mathrm{O}((\log T)^c)$ for some constant $c>0$).

Recall that the contexts $x_t$ are independent across time, implying that the distribution of the reward feature $\phi(x_t,\omega_{at})$ is independent of $\mathcal{F}_{t-1}$. Assumption (ref) leverages this independence to impose an anti-concentration condition that rules out degenerate reward features. Informally, every one-dimensional projection of $\phi(x_t,\omega_{at})$ must have nontrivial variation near zero. This condition is imposed because $\theta_*$ is learned only from selected outputs, whereas the index loss for box $a$ uses queried outputs. Thus, the reward features must be sufficiently informative for evaluating the queried features that enter the index estimator. For example, it is satisfied when the embedding distribution is a truncated Gaussian, a truncated multivariate Student's $t$, or a uniform distribution on a hyperrectangle; see Lemmas (ref)--(ref) in Appendix (ref).

The following lemma bounds the additional perturbation caused by using $\hat\theta_{t-1}$ in the index loss.

Lemma (ref) shows why Assumption (ref) is needed. The first term on the right-hand side has the same quadratic form as the population curvature in Lemma (ref) and can therefore be absorbed into the curvature argument. The second term is the reward estimation error evaluated on queried outputs. By Lemma (ref), this term is controlled by the inverse-design norms $\|\phi(x_s,\omega_{as})\|_{\Phi_{t-1}^{-1}}$, where $\Phi_{t-1}$ is constructed from previously selected outputs, while $\phi(x_s,\omega_{as})$ corresponds to queried outputs used for estimating the index of box $a$. Thus, there is a potential mismatch between the selected outputs that inform reward learning and the queried outputs that enter index estimation. Assumption (ref) rules out severe mismatches of this form by ensuring that $\Phi_{t-1}$ is sufficiently well conditioned, so these inverse-design norms do not remain large.

We now state the confidence bound for the index estimator:

The proof follows the same localized empirical-process argument as Proposition (ref). By the optimality of $\hat\rho_{at}$ in (ref), $\sum_{s\in\mathcal S_{at}} \left\{ \hat\ell_{as,t}(\hat\rho_{at}) - \hat\ell_{as,t}(\rho_a) \right\}\leq0$. Decomposing this into the oracle population curvature, the empirical fluctuation, and the plug-in perturbation gives $$\sum_{s\in\mathcal S_{at}} \mathbb E\!\left[ \ell_{as}(\hat\rho_{at})-\ell_{as}(\rho_a) \,\middle|\, \mathcal F_{s-1},x_s \right] + H_{at}(\hat\rho_{at}) + J_{at}(\hat\rho_{at})\le0.$$ The first term is lower bounded by the curvature result in Lemma (ref), the second is controlled by the empirical-process bound in Lemma (ref), and the third is controlled by Lemma (ref) together with the reward confidence bound in Lemma (ref). Combining these bounds yields (ref). The detailed proof is provided in Appendix (ref). Motivated by Proposition (ref), define the optimistic reservation index as

Since $\Lambda$ is increasing, Proposition (ref) implies that, with probability at least $1-\delta$, $\widetilde{\sigma}_{at} \ge \Lambda(\rho_a^\top\psi(x_t)) = \sigma_{at}^*$ uniformly over all $a\in[A]$ and $t\in[T]$.

Regret Analysis under Unknown Reward Function

We now combine the reward and index confidence bounds to control the cumulative regret of COSMOS\ when the reward function is unknown. The preceding subsections established two high-probability optimism events: Lemma (ref) gives optimism for the reward estimate $\widetilde{\mu}_t$, and Proposition (ref) gives optimism for the reservation index estimate $\widetilde{\sigma}_{at}$. Therefore, when both events hold, the regret decomposition in Theorem (ref) applies and separates the period-$t$ regret into a reward estimation term and an index-estimation term for all $a\in[A]$ and $t\in[T]$. This structure parallels the known-reward analysis in Section (ref). When the reward function is unknown, an additional generalized linear bandit term appears from estimating the reward parameter.

As shown in Appendix (ref), Assumption (ref) implies that, with high probability, $\lambda_{\min}(\Phi_{t-1}) \ge \frac{t-1}{16\,\mathrm{polylog}(T)}$ uniformly for all $t\ge \tau:=C\mathrm{polylog}(T)\log(Ad)$ for some absolute constant $C$. This eigenvalue growth allows the reward estimation error in $J_{at}(\rho)$ to be controlled uniformly over $t\geq\tau$, so that the cumulative regret is controlled after $t\geq\tau$. For these initial periods before $\lceil\tau\rceil$, the per-period regret is bounded by $(2A+1)$. Since $\tau=\mathrm{O}(\log(Ad)\mathrm{polylog}(T))$, so the cumulative regret up to period $\lceil\tau\rceil$ is at most $\mathrm{O}(A\log(Ad)\mathrm{polylog}(T))$, and is therefore dominated by the regret accumulated over periods $t\ge \tau$.

The terms in Theorem (ref) correspond directly to the two components in Theorem (ref). The term $\widetilde O(d\sqrt T)$ is the reward estimation regret, matching the usual dimension dependence for generalized linear contextual bandits with reward feature dimension $d$. The term $\widetilde O(A(m+\sqrt{dm})\sqrt T)$ is the index-estimation regret, where $A$ is the number of boxes and $m$ is the dimension of the index feature $\psi$. Relative to the known-reward case in Proposition (ref), the additional term $\widetilde{O}(A\sqrt{dmT})$ reflects the effect of reward estimation error on index estimation. On the high-probability optimism event, Theorem (ref) gives $\mathbb{E}\left[\sum_{t=1}^T \Delta_t(\tilde\pi)\right] \leq \mathbb{E}\left[\sum_{t=1}^T \left\{ \widetilde{\mu}_t(x_t,\omega_{a_t t})-\mu^*(x_t,\omega_{a_t t}) \right\}\right] + \mathbb{E}\left[\sum_{t=1}^T \sum_{a\in\mathcal A_t} \left( \widetilde{\sigma}_{at}-\sigma_{at}^* \right)\right].$ The first sum is controlled by the reward confidence radius from Lemma (ref) and an elliptical-potential argument abbasi2011improved for the reward-design matrix $\Phi_{t-1}$. The second sum is controlled by the index confidence radius from Proposition (ref) and a separate elliptical-potential argument for each box-specific design matrix $V_{at}(\eta_1)$. Thus the unknown-reward analysis adds a standard reward-learning term while preserving the same index-learning rate as in the known-reward benchmark. The detailed proof is provided in Appendix (ref).

Conclusion

Motivated by LLM cascading, we introduce an online contextual Pandora's Box model in which a decision-maker sequentially queries APIs to generate outputs at a cost and deploys a single output, observing only its downstream reward. This output-mediated feedback departs from the classical setting, where opening a box reveals its reward directly, and captures a key feature of LLM cascading systems: API-specific heterogeneity enters only through the distributions of generated outputs and costs, while downstream value is governed by a shared reward evaluator on the context-output pair. Rather than estimating the full conditional output and cost distributions, we impose a generalized linear structure directly on the reservation indices and the shared reward function. Our COSMOS\ policy is built by combining GMM estimation of the reservation indices with UCB-style confidence bounds for both the indices and the reward evaluator. Through a regret decomposition under optimism, which separates cumulative regret into reward-estimation errors for deployed outputs and index-estimation errors for queried APIs, we derive a $\widetilde{\mathrm{O}}\left([d+A(m+\sqrt{dm})]\sqrt{T}\right)$ regret bound.

Our work opens several avenues for future research. First, because our theoretical guarantees rely on generalized linear specifications, extending the moment-based UCB framework to richer nonparametric or neural representations is a natural next step. Achieving this while preserving $\widetilde{O}(\sqrt{T})$ regret would further broaden the model's applicability. Second, our current formulation assumes a standard LLM cascading structure where APIs are queried sequentially and a single output is selected and then deployed. Expanding this framework to allow for batched querying under latency budgets, or to support output ensembling and synthesis, would significantly change the query-selection dynamics. Addressing these richer action spaces raises compelling new questions about the structure of the learning policy.

AI Disclosure

The authors used generative artificial intelligence tools, including GPT, Gemini, and Claude, to edit and polish earlier versions of the drafts. All AI-generated text and suggestions were checked, revised, and approved by the authors. The authors take full responsibility for the accuracy, integrity, and originality of the submitted work.

Acknowledgment

We thank Ali Makhdoumi for helpful discussions on the general theory and intuition of Pandora’s Box, and Shreyas Sekar for an early conversation on AI-assisted coding and model selection for reducing LLM API costs that eventually led us to the FrugalGPT paper by chenfrugalgpt. We also thank the participants from 2026 Marketplace Innovation Workshop for comments and discussion.