Online Decision Making with Generative Action Sets
Authors: Jianyu Xu
Vidhi Jain
Bryan Wilder
Aarti Singh
Venue: ICLR 2026 Poster (2026)
Keywords: online decision making
create-to-use
Primary area: learning on time series and dynamical systems
TL;DR: We propose a doubly-optimistic online learning algorithm that learns when to generate new actions versus reuse existing ones, achieving the first sublinear regret bound.

Abstract: With advances in generative AI, decision-making agents can now dynamically create new actions during online learning, but action generation typically incurs costs that must be balanced against potential benefits. We study an online learning problem where an agent can generate new actions at any time step by paying a one-time cost, with these actions becoming permanently available for future use. The challenge lies in learning the optimal sequence of two-fold decisions: which action to take and when to generate new ones, further complicated by the triangular tradeoffs among exploitation, exploration and *creation*. To solve this problem, we propose a doubly-optimistic algorithm that employs Lower Confidence Bounds (LCB) for action selection and Upper Confidence Bounds (UCB) for action generation. Empirical evaluation on healthcare question-answering datasets demonstrates that our approach achieves favorable generation-quality trade-offs compared to baseline strategies. From theoretical perspectives, we prove that our algorithm achieves the optimal regret of $O(T^{\frac{d}{d+2}}d^{\frac{d}{d+2}} + d\sqrt{T\log T})$, providing the first sublinear regret bound for online learning with expanding action spaces.

Published as a conference paper at ICLR 2026
ONLINE DECISION MAKING WITH GENERATIVE ACTION SETS
Jianyu Xu, Vidhi Jain, Bryan Wilder, Carnegie Mellon University Piusburgh, PA 15213 (jianyux, vi vidhij2, j2, bwilder, aart i a Bandrew. cww.ccc........ooeee
Aarti Singh
ABSTRACT
With advances in generative AI, decision-making agents now dynamically create new actions during online learning. but action generation typically incurs costs that must be balanced against potential benefits. We study online learning problem where an agent can generate new actions at any time step by paying a one-time cost, with these actions becoming permanently available for future use. The challenge lies in learning the optimal sequence of two-fold decisions: which action to take and when to generate new ones, further complicated by the trian- gular tradeoffs among exploitation, exploration and creation. To solve this prob- lem, we propose doubly-optimistic algorithm that employs Lower Confidence Bounds (I.CB) for action selection and Upper Confidence Bounds (UCB) for ac- tion generation. Empirical evaluation on healthcare question-ansseriin datasets demonstrates that our approach achieves favorable generation-quality tradeoffs compared to baseline strategies. From theoretical perspectives, we prove that our algorithm achieves the optimal regret of ( पमंर + d 7),, providing the first sublinear regret bound for online learning with expanding action spaces.
INTRODUCTION
Sequential decision-making problems involve agents repeatedly selecting actions from a candidate set to maximize cumulative reward. Traditional approaches assume fixed set of available actions, focusing on the exploration-exploiae ploitation) against less-tested alternatives (exploration). However, advances in generative Al have introduced new paradigm where contemporary systems can dynamically expand their action spaces by creating novel actions over time. This capability introduces an additional strategic dimension that agents should also balance immediate performance with strategic investments in future capabiliitess enabled by new actions. Consider the following motivating scenarios:
tradeoffs: balancing empirically high-reward actions (ex-
Example 1.1 (Healthcare Question-Answering Systems). Al- Al-powered healthcare platforms must decide between reusing existing vetted responses from their FAQ libraries or investing in creat- ing new, tailored responses for novel patient inquiries. Each custom response requires costly expert review and validation (potentially hundreds of dollars when accounting for clinical expertise). How- ever, once created and vetted, these responses become reusable assets. When a patient given region asks "What are healthy meals during pregnancy?" the system fasee a critical choice: provide a generic response about pregnancy nutrition, or invest in creating a new response more specific to typical foods in that region, benefiting hundreds of future expectant mothers in similar settings.
Example 1.2 (Personalized Advertisement). An advertising platform may initially start with finite set of ad templates for different user contexts. Over time, the platform observes new user segments and decides design specialized ads (with initial design and production costs) perfectly customized to the new user subgroups. Once created, these specialized ads become available for future targeting no additional cost.
In both scenarios, the agent must decide at each time step whether to select existing action pay a one-time cost to instantiate a new action perfectly suited to the observed context. This introduces novel create-to-reuse problem that goes beyond traditional exploration-exxloiiation tradeoffs.

---

Published as a conference paper at ICLR 2026
Problem Formulation (preview). We study online learning problem with expanding action space. At each time t, the agent first observes context Iz.. Then it may either
(a) Select an existing action, incurring some (potentially suboptimal) loss, or
(b) Generate a new action that is customized the current Zy (without any excess loss), at fixed one-time cost.
This formulation has two key features. First, step (b) is notable in that the agent generates new action only through an oracle A(zz) that is prompted by the context 2₁. The learning algorithm operates a decision-making layer top of this custom action oracle. In contrast, traditional online learning or bandits operate directly in the action space. Second, once generated, new actions can be reused in future rounds without additional expense. The key is to judiciously decide when to pay the cost of adding such a specialized action and when to rely on existing arms.
This setting presents fundamental challenges that distinguish it from existing online learning and bandits frameworks. We face a triangular tradeoffs among three competing objectives: exploitation (using known good actions), exploration (leaming about existing uncertain actions), and creation (generating a new action to satisfy immediate needs while enriching future capabilities). Addi- tionally, we have no prior experience with potential new actions unlimited freedom generate arbitrary ones each creation must be specifically tailored to the current context at fixed cost.
Summary of Contributions
Our main contributions are fourfold:
1. Problem Modeling: We establish a new problem formulation that allows for costly expan- sion of the action space in online learning, formalizing the create-to-reuse framework.
2. Algorithmic Framework: We propose doublly-otimmistc algorithm that Lower Confi- dence Bounds (LCB) when selecting among existing actions, and Upper Confidence Bounds (UCB) when deciding whether to generate new actions. This design simultaneously exploits near-optimal actions and enables creation without excessive hesitation.
3. Empirical Validation: We conduct experiments on real-world healthcare question- answering datasets, demonstrating that our approach achieves favorable ceneration-qualit tradeoff's compared to baselines. Our results show the method gracefully interpolates be- tween pure reuse and always-create policies while maintaining superior performance.
4. Optimal Regret Guarantees: Under a semi- parimearamttric loss model, our algorithm achieves O(T 442 d=#2 + d/Tlog T) expected regret, where T is the time horizon and d is the di- mension of covariates. We prove this rate is optimal by establishing a matching Q2T 24अ information-theoree lower bound.
Technical Novelty. The crux of our approach is double optimism principle, which resolves unique challenge of balancing creation with exploration/exploitaion. Among existing actions, we rely their LCB comparisons to both exploit high-perforning actions and continue exploring uncertain ones. When evaluating creation decisions, we compare the UCB loss the best exist- ing action against the fixed generative cost, triggering creation with appropriate probability. This double optimism perspective naturally maximizes the long-term value new actions while tightly controlling worst-case regret.
The rest of this paper is organized as follows. We discuss related literature in Section then present the rigorous problem setting in SeetionBalong with the necessary assump- tions. We propose main algorithm in Section 4 analyze its theoretical performance in Section and conduct numerical experiments to validate its weal-woldd performance Section 6
Paper Organization.
2 RELATED WORKS
Here discuss related literature the most relevant topics in online decision making. Please refer to Appendix [ discussions on broader fields including bandits with knapsacks, active learning, and digital healthcare.
2

---

Published as a conference paper at ICLR 2026
Multi-Armed and Contextual Bandits. The multi-armed bandit (MAB) problem has been exten- sively studied since Lai & Robbins 1985). The classic framework (Auer et al. 2002 Agarwal et al, 2014), that decision-maker repeatedly selects from fixed set of arms, was extended to contextual bandits (Li et al. 2010 Chu et al. 2011) where rewards depend on observable contexts. The crux is to balance exploration and exploitation with the goal of regret minimization. Please refer to Slivkins et al. (2119) for a comprehensive discussion.
Online Facility Location. Online facility location (OFL), studied by Meyerson (2001). Fotakis (208), and Guo et al. (2020), is closely related to our formulation. In OFL, algorithms decide whether to open new facilities or assign requests existing ones, minimizing facility costs plus assignment distances. While structurally similar to our problem, there are crucial differences. First, OFI. assumes known distance metrics, while we must learn unknown parameters defining distances. Second, automatiicly assigns points to nearest facilities, while we must actively select actions under uncertainty. Therefore, OFL, involves two-way trade-offs between immediate costs and future benefits, whereas our problem requires three-way balance between exploitation, exploration, and creation, necessitating our novel algorithmic approach.
3 PROBLEM SETUP
We now formalize the problem of creating-to-reuse order to demonstrate the problem setting, we start with the healthcare Q&A scenario described in Example I.1 As an abstraction, each arriving patient question represented as a d-dimensional context vector re in a learned semantic embedding space. The system maintains a context library S, of vetted FAQ entries, implemented
online decision-making framework. In
hash table where each context that has been previously added serves as a key to its corresponding custom respond (or generally the action) generated by an oracle A(-). Crucially, the algorithm operates only in the context representation space by searching through context keys in S.. When new question 2ez arrives, the algorithm makes decisions based on estimated losses and can either:
(a) Decide to create new custom response by paying a fixed cost and adding context Ty as new key to the library. The generation oracle A(-) then automatically produces the tailored action 0₁ A(re), and the pair (I',, a:) becomes permanently available for future reuse. Or
(b) Select existing context key f S; from the library. The system automatically retrieves the corresponding action a, = Sx = A(f) and deploys it for context vt, incurring mismatch loss d(r,, f') that reflects the difference between (1) the custom response context Ta versus (2) the action tailored for another context f.
Technically, we consider the following problem setting.
Initialize: A library S = (ʃ. A(T) with context keys ʃ and vetted custom actions A(J).
Fort = 1.,,..,,':
1. Observe x, E Rd (patient question arrives).
2. The algorithm decides whether to create a customized response to xt. If YES, then
(i) Generation oracle produces and deploys a; = A(xx) (custom response to 2t).
(ii) Receive fixed loss e (creation cost).
(iii) Update S.+1 := S₁ U {æt : )t) (add new context-action pair to the library).
3. If NO, then
(i) Select an existing context key fe S2 and retrieve o, S.(ff)).
(ii) Receive loss 1 := d(z;,f) fe) + N₁ (noisy mismatch penalty).
(iii) Update S := Sy (library unchanged).
In this formulation, d(z,, ft) captures the expected mismatch loss when deploying an action orig- inally designed for context to context rz. While this fundamentally reflects the difference between A(x;) and A(f.) in the action space, the algorithm can only estimate this through context- space relationships since it lacks direct access A(xx)) (actions having not been generated yet).
3

---

Published as a conference paper at ICLR 2026
For theoretical analysis, our main modeling assumption is that this mismatch be captured by a squared distance function in the context space. In experiments, we consider other forms for the mismatch distance.
Assumption 3.1 (Quadratic parametric loss). We assume the distance function satisfies d(z, f) == (z f) (x
(1)
where W $ is an unknown positive semi-definite d x matrix. Accordingly, denote
w :>Vc<(W E RRd o(r, = ==Vecle - f)(x - = ERR,
(2)
and we have equivalent definition d(x, = 6(x, f)ww.
Why we assume a quadratic parametric loss? The motivation is that contexts are embedded in space where different dimensions capture semantically relevant information. The cost of reusing an action designed for one context when serving another can be modeled as a distance on this representation space, although the exact importance weighting of different semantic dimensions (captured by matrix W) is unknown to the learner. Since d(æ,, 2z) = O, our formulation measures the excess cost due to not generating a custom action for each æt-- This fits scenarios where the algorithm interacts with complex action spaces through oracle A(xx) (human expert or generative model); our aim to achieve good performance relative to this oracle's capabilities. Modeling d(::-) as squared distance function captures more structure than linear parametric choices while remaining more tractable than nonparametric formulations. Furthermore, the empirical results our algorithm performs weal-world Hcalthcare Q&A datasets validate the robustness of this modeling.
Goal of Algorithm Design, Our goal is to minimize the expected total loss. We will rigorously define the performance metric and technical assumptions at the beginning of Section 5
4 ALGORITHM
To solve this online decision-making problem with expanding context libraries, we propose "Doubly-Opimmistic algorithm. This section presents the algorithm design and highlights its prop- erties. We will analyze and bound its cumulative regret in the next section.
The pseudocode of our algorithm is displayed in Algorithm At each time t. the algorithm inherits loss estimation parameters E, b;-1 [ and context library S, from (t 1), then observes new context vector It. Using the estimation parameters, computes predicted mismatch loss (x,,,, f' and uncertainty bound 4x f) for each existing context key E St. The algorithm operates entirely in the context representation space and takes the following two steps to determine which action deploy.
Lower Confidence Bound (LCB) loss on existing contexts. For each existing context key f. we calculate the LCB loss as de (x f) (x f) Ax f). We then select fa as the context key with the minimum LCB loss. Note that we do not immediately choose to reuse this context.
(ii) Upper Confidence Bound (UCB) probability to create new entry. After identifying f: as the best existing option, turn consider its UCB loss (1 fi) de( fi) (m,, fi) and compare it against the fixed creation cost c. With probability of min(1, d((x). }. we decide to create new entry: The oracle generates a, = A(xx)) and we add context x; to the library. Otherwise, we reuse the existing context fr. and the system retrieves a, = S. [fa] from library S.. After receiving a mismatching loss 4, the algorithm update the estimation parameters E, and b, accordingly.
As the argmin of LCB loss, fa represents the existing context that could potentially yield the low- est mismatch under optimistic assumptions, balancing exploration and exploitation given historical uncertainties. This approach aligns with contextual bandit methods such as Chu et al. (001))
I Lincar regression parameters. We estimate the vector to as 5-1 b every time step f.
4

---

end for Published as a conference paper at ICLR 2026
Algorithm Doubly-Optimistic Algorithm
1: Initialization: Custom action oracle A(x), and Eg = X he = = = -T A(Ta)). a
2: for 1.,....,7 do
3: Observe context 2; E IRd
4: Vorvf- St (all existing context keys) do
5:
Compute loss estimates and uncertainties. Denote
Ar(x, a. Vo(ee. f) ET f), d( 6(2.f) b " (3) d(xxf)= dx f) (2,
de(z,)) dz, + 41 f).
6:
7:
Select context key ft := arg min f E Sxdi
8:
if Z. --=1 with Z. (er(min(1, de(a,, [i)]) an i.i.d. Bernoulli random variable
then
9:
Decide to create new: Oracle generates action a, A(x;) and deploys it cost Receive loss 4 = (perfect match for custom action).
10:
11:
Update context library 5t-1 St U Ft de (add new context-action pair). Keep Σ == Et and b, == b without updating.
12:
else
14:
Decide to reuse: Retrieve and deploy action dr St = A(ft) at no creation cost. Receive mismatching loss d(xt, ft) + Nr.
16:
Maintain context library S1+1 = St (no new entries).
Update loss estimation parameters
D3 Σ + p(2,, fi)o(ar S be + o(Fr,
18:
end if end for
19:
The UCB-based creation probability de(ze.fe) increases the chance of adding contexts when the estimated mismatching loss is high relative to creation cost (within risk A, we can tolerate). This design enables to estimate the "necessity" of creating new entries while bounding the total expected loss accumulated before any new context is added to a particular region of the context space. We explain this property later Lemma B.5
Computational Complexity I incurs worst-case time complexity (dd'T2), as it com- pute matrix-vector products of d² dimension for every context key f E St at each round with at most T contexts possible. Since the expected number of newly created contexts is O(Ta#z) (+2) with respect to T, the expected complexity refines to O 2d
Given that d can represent sentence em- bedding dimensions in the Q&A scenario, O(d*) time complexity impractical. In real-data numerical experiments, we improve computational performance by replacing the estimated distance function d, (v., f) with either of the forms:
(a) A squared linear model (0T (x= (cquivalent to setting W = 00TT) reducing the computa- tional complexity to (dd)). Uncertainty bounds are derived from ridge regression covariance matrices.
(b) A neural network d(x, f: θ) with uncertainty function A. fi 9) derived under Gaussian conjugate assumptions, reducing complexity to O(D²) where D := ||O||o is the number of NN parameters.
On the other hand, we implement the original algorithm in the synthetic-dee simulations to validate the theoretic guarantees with respect T (for small d's only).
THEORETICAL ANALYSIS
In this section, we provide a regret analysis of our algorithm. We first state the performance metric and necessary technical assumptions. Then present the main theorem the algorithmic regret
5

---

Published as a conference paper at ICLR 2026
upper bound. Finally, provide corresponding lower bound that matches the leading term of the upper bound with respect to T'
5.1 DEFINITIONS AND ASSUMPTIONS
As have stated by the end of Section 3 our goal minimize the total loss. In order measure the performance, we adopt the expected regrel as the loss metric, which is defined as follows: Definition 5.1 (Optimal and Regret), Denote the minimal expected los Toseahhe that is achievable hind- sight as OPT, which equals:
T
min OРТ. == S:= Sr. Stt1 (.C((+))
c. ST
Σ min d(xs, f). SES.
(5)
There also exists a non-achievable minimal loss denoted as OPT, which only accessible by an omniscient oracle that knows {xr)t=1 and selects an optimal option set ahead of time:
T
OPT. := min c. |S| +
Σ
min d(It, f).
(6)
FES
From the definition, we know that OPT. OPTh algorithm as ALG, which equals:
Also, denote the expected loss obtained by our
r
ALG:= = 1S +
min d(z,, f).
Define the regret REG as the expected loss difference between OPT, and ALG.
REG := -PALG-OPHI
We then make two distributional assumptions on the covariates and the noises, respectively.
Assumption 5.2 (Covariate distribution and norm bound). Assume Ti R 1, 2......77 T drawn from independent and identical distributions (i.i.d)), with d 2 2. Also, assume a norm bound | < 1.
Assumption 5.2 is necessary for us to effectively learn the metric matrix W through online linear regression. For the same reason, we assume subGaussian noise on the observations follows:
Assumption 5.3 (Noise distribution). Assume that Ne R. 1,2...., T are drawn from subGaussian i..dd. where a is universal constant.
5.2 REGRET BOUNDS
In this subsection, sequentially present our theoretical guarantees on the regret upper and lower bounds, as the following two theorems.
Theorem 5.4 (Regret upper bound). With assumptions made in Section 5.1 the expected regret of our Algorithm is upper bounded by - + do)
Proof Sketch. We prove Theorem 5.4 in the following sequence:
1. (Lemma B.1 We upper bound the non-achievable minimal loss as OPT, 0(T क=ス d This is proved by fine-grid covering of the space.
2. (Lemmal B.3)
We upper bound the algorithmic loss ALG within constant competitive ratio of OPT, adding cumulative prediction errors: E[ALG] = (EE + +Σ (x, To prove this, divide {xx 's into "good" and "bad" groups, and bound their excess loss respectively.
'Expectation taken over observation noises only, Same for the definition of OPT. Expectation taken the {x,) )7 series.

---

Published as a conference paper at ICLR 2026
Novert Rano Noveratel 2-257-38550 N-13
Novel fato hosmrtcle 0-377-38950
Novel Aovmratel www...022000000
Agetto
(a) 2
(b) d =d=3
(c) d=
Figure 1: Regret curves for T' 10000 and d 2, 3, 4 in log-log scales, repeated by N 10 epochs. The slope of the linear asymptote under log-log diagram indicates the power dependence of regret on T, which should be 4+2'
3. (Lemma B.8
O(d/Tlog by standard online linear regression (similar to Chu et al. 2201 by replacing d with d²).
We upper bound the excess risk E t-1 (zt,,
4. Finally, we derive the regret upper bound as REG = E[ALG OPTN = O(Taia daiz + log') T) according to the three steps above.
Please refer to Appendix B for all technical details of this proof, including rigorous statements of lemmas and derivations of inequalities.
To show the optimality of the regret upper bound proposed above, we present the information- theoretic lower regret bound.
Theorem 5.5 (Regret lower bound). For any online learning algorithm, there exists instance of problem setting presented Section such that the regret is at least (T(T with respect to T (despite the dependence on d).
à) lower bound for the K n-nearest-neighbors (K-NN) problem, along with optimal choice of K that balance this term
We defer the proof Appendix B.6 The main idea is to apply the 22K
with e K. Theorem 5.5 indicates that our algorithm achieves an optimal regret with respect to T.
6 EMPIRICAL PERFORMANCE
In this section, conduct numerical experiments validate method's performance. We first run the original algorithm on dimmensiionnl synthetic data to demonstrate the regret dependence on T. Then adapt our algorithm real-world healthcare Q&A scenarios and show better trade- offs between generation cost and mismatching loss compared to baselines.
6.1 REGRET VALIDATION SYNTHETIC DATA
We evaluate doubly-optimistic algorithm synthetic data with dimensions d = 2,3, 3,4 4 over time horizon = 10, 000, repeated for N = 10 epochs. Context vectors Hy are drawn from Lz-normalized uniform distributions, with noise N₂ (O0 0.05). We calculate regret by com- paring the algorithmic loss against OPT, (defined in Equation (6). approximated by randomized K-means++ with Lloyd iterations over potentially optimal values of K. We do not apply OPT, as its computational cost is exponentially dependent on T.
Figure presents the regret curves in log-log scale reveal the power dependence of regret T. Our method exhibits empirical slopes of 0.447, 0.576, 0.676 for d = 2,3,4 respectively, aligning closely with the theoretical rates which should be of according to Theorem 5.4 These results validate theoretical analysis in synthetic environments.
Note: We restrict experiments to low-dimensional settings due to the computational cost of OPT, (a necessary component of regret) in high dimensions, where K-means++ becomes ineffective and the

---

Published as a conference paper at ICLR 2026
Generation vs Nismatching Trade-offs
Generation vs Mismatching Trade-offs
Nomalige cum cunolativ manianannmmaaaii mammmmmmmtttt 1032
Our method
homalige cumuiatt mnter intemaati last
Our mothod
method 951
9516
0.8
6.0
generation every
generation every
2.6
FiceddIf baselie
6.6
Ficed-P baselime
0.4
0..4
62
0.2
0.0
0.7
0.4
2.6
1.0
6.0
0.7
0.4
0.5
3.0
fraction newt responses generattd
fraction nee responses generated
Numerical results on private maternal (b) Numerical results on the public health Q&A datasct.
Medical Q&A Datasct
Figure 2: Tradeoffs between normalized generation costs (x-axis) and normalized mismatching loss (y-axis) on two healthcare Q&A datasets. A lower/left curve indicates a better performance. Each blue point represents the (generation cost, mismatching loss) pair caused by a choice of In both cases, our algorithm outperforms the baseline that randomly generates custom responses with a variety of fixed probabilities p (each gray point represents choice of p).
underlying nearest neighhor problem is NP-hard. Despite these computational limitations, the syn- thetic validation confirms that approach achieves the predicted theoretical regret rates, providing confidence its performance for dnderaat-dimensional real-world applications.
6.2 CONEERATION-UUAIII TRADEOFFS ANALYSIS ON HEALTHCARE Q& DATASETS
We evaluate our algorithm on two real-world healtheare Q&A datasets demonstrate its practical effectiveness:
1. Private Maternal Health Dataset: A dataset containing 839 user queries, with 12 pre- written FAQs for pregnant women, provided by a company developing healthcare chatbots.
2. Medical Q&A Dataset: A public collection of 47,457 medical question-answer pairs curated from 12 NIH websites Ihttps://www kawgle com cttm///taaaettssgaaaceeeeetorrre cancer-gr-and-a--aataae
Experimental Setup. Our experimental framework models the create-to-reuse decision process operating entirely in the context representation space. All questions mapped embeddings using OpenAl's pre-trained text -embeddingg 3-small model, creating a semantic representation space where the algorithm makes decisions. For each arriving question context I;, the algorithm decides whether to select an existing context key f from the FAQ library or add x, as new context key and then invoke the custom answer generation oracle A(-).
Custom answer generation differs across datasets to reflect their nature. For the maternal health dataset, custom answers are generated by GPT-5 with carefully designed prompts including safety guardrails and emergency detection protocols appropriate for healthcare contexts. For the Medical Q&& dataset, custom answers are directly retrieved from the pre-existing responses associated with each question entry.
Crucially, the mismatch loss feedback occurs in the action space rather than the context space. For current question context and an existing context in the FAQ library, the loss is calculated as (1-cosine similarity) between Iz's custom answer and f's custom answer. This reflects our core assumption that the algorithm operates in context space while true loss manifests in action space, accessible only through the generation oracle A(.).
As also mentioned in Section 4 maintain computational tractability, model the estimated loss function as d(x,, f) = (#T(s (x f) (on the maternal health dataset) or adopt neural network d(z, f: () (on Medical Q&& Dataset).
We evaluate our doubly-optimisthe algorithm against a fixed probabiibbabiity baseline strategy. This base- line makes i.i.d. Bernoulli decisions ~ Ber(p) at each time step: with probability p. generate
8

---

Published as a conference paper at ICLR 2026
tom response; otherwise, select the most similar existing context from the library based cosine similarity between question embeddings (note that has no access to the custom answer before gen- eration). To comprehensively evaluate performance across different cost-aceuracy preferences, vary the probability parameter uniformly across [0, 1] for the baseline. Meanwhile, we also vary the creation cost parameter from 0 to 100 for algorithm, generating complete tradeoff curves for both approaches.
The numerical results are depicted in Figure 2 where points and curves closer the bottom-left indicate superior performance. We plot cumulative generation costs against cumulative mismatch losses, with both metrics normalized separately to [0, scale for interpretability. Generation costs are normalized by the total cost of the diways-generate strategy, while mismatch losses are normal- ized by the status quo strategy that never generates custom responses. Note that these represent the two components of total loss in our formulation, depicted separately for clearer analysis. Each gray point represents a different choice of p for the baseline, forming a curve that represents the best possible performance achievable by any fixed-probability strategy. Each experiment runs N 10 epochs with 95% confidence intervals computed using Wald's test.
Results on the Maternal Health Dataset. Figure 2a presents the generation-quality tradeoffs. Starting with 12 pre-written FAQs, our algorithm demonstrates several key advantages:
1. Context Clustering: Compared with the
strategy (green triangle), ap- proximately 30% of user questions exhibit sufficient similarity to existing FAQs, as evidenced by the algorithm achieving near-zero mismatch loss when generating responses for 70% of queries.
2. Efficiency Gains:
Compared with status quo (red triangle), strategic addition of just a few targeted FAQs reduces mismatch loss by approximately 25% (as evidenced by the algorithmic curve approaching the point (0, 0.75)), highlighting the value of adaptive creation decisions over static policies.
3. Pareto Optimality: Our algorithm consistently outperforms fixed-probability baselines throughout the entire generation spectrum, with statistical significance demonstrated by 95% confidence intervals. The doubly-optimistic approach effectively pushes the performance frontier toward Pareto optimality.
Results on Medical Q&A Dataset. We establish the initial FAQ library by prompting GPT-5 to classify all questions into 32 categories by topic, then randomly sampling 10 question-anss answer pairs from each category to create generic response (a total of 32 FAQs).
presents results on the public Medical Q&A dataset.
Compared with the always- generraingn and FAQ-only baselines respectively, our algorithm can re- duce about 60% generation cost and about 60% mismatch loss, leading to positive-sum tradeoffs (indicated by the convex curve). Also, it achieves statistically significant improvements over fixed- probability baselines across nearly the entire generation spectrum, confirmed by 95% confidence intervals. However, the performance gains are notably smaller than those observed on the private maternal health dataset. We attribute this difference the greater diversity in the Medical Q&A dataset, spanning 37 question types across 32 medical topics. In contrast, the private dataset focuses specifically maternal health with more concentrated topics and frequently recurring keywords, producing clearer semantic connections and stronger correlations between context and action simi- larities that enable more effective learning.
The results validate our theoretical framework in practice, demonstrating that principled confidence bound approaches for creation decisions significantly outperform heuristic alternatives in real-world healthcare applications where both response quality and resource efficiency are critical.
7 CONCLUSION
In this paper, we introduced an online dicision-makinge problem where new actions can be generated on the fly, at a fixed cost, and then reused indefinitely. To address the balance among exploitation, exploration, and creation, we proposed opphiy-op algorithm that achieves O +

---

Published as a conference paper at ICLR 2026
log I) regret. This regret rate proved optimal with matching lower bound, and was validated through simulations. We also implemented our algorithm on a real-world healtheare Q&A dataset make decisions generating answers v.s. applying FAQ. Our results open up avenues for optimizing creation decisions in online learning, with potential extensions to broader loss models and flexible creation costs.
ETHICS STATEMENT
This research is in accordance with the ICLR Code of Ethics. Our work does not involve human subjects. We use one public dataset under MIT license and one private dataset with proper authoriza- tion from the data owner. The proposed methodology is designed benefit users through improved healthcare Q& systems, with no identified potential for harm. We have conflicts of interest to report, and all experimental procedures comply with relevant data usage agreements and licensing terms.
REPRODUCIBILITY STATEMENT
We have made comprehensive efforts to ensure the reproducibility of our work. All experimental details, including dataset specifications, preprocessing and initialization, evaluation metrics, and sta- tistical significance, are provided in the main text and appendix. Complete algorithmic descriptions and implementation details are included throughout the paper. All theoretical results are accompa- nied by full proofs in the appendix, with clearly stated assumptions. We commit releasing the complete source code upon acceptance of this paper. The public dataset used in our experiments is available under MIT license, and we provide detailed descriptions of all data processing steps and experimental procedures to enable replication of our results.
ACKNOWLEDGMENTS
This work is partially supported by the Engler Family Foundation and the NSF Al Institute for Societal Decision Making (NSF AI-SDM, Award No. 2229881). We appreciate the input from Nivi. Inc for providing the maternal health dataset.
REFERENCES
Alekh Agarwal, Daniel Hsu, Satyen Kale, John Langford, Lihong Li, and Robert Schapire. Taming the monster: A fast and simple algorithm for contextual bandits. International Conference on Machine Learning (ICMI.-14), pp. 1638-16444 2014.
Shipra Agrawal and Nikhil Devanur. Linear contextual bandits with knapsacks, Advances in neural information processing systems, 29, 2016.
Dana Angluin. Queries and concept learning. Machine learning, 2(4):319-344 342, 1988.
Peter Auer. Using confidence bounds for exploitation-exxplrraioo trade-offs. Journal of Machine Learning Research, 39Nov):397-422, 2002.
Peter Auer, Nicolo Cesa-Bianchi, and Paul Fischer. Finite-time analysis of the multiarmed bandit problem. Machine learning, 47(2):235-256, 2002.
Ashwinkumar Badanidiyuru, Robert Kleinberg, and Aleksandrs Slivkins. Bandits with knapsacks. In Anmual Symposium on Foundations of Computer Science (FOCS-I3), pp. 207-216. IEEE, 2013.
Richard Bellman. Studies in the mathematical theory of inventory and production, 1958.
Heng-Tze Tze Cheng, Levent Koc, Jeremiah Harmsen, Tal Shaked, Tushar Chandra, Hrishi Aradhye, Glen Anderson, Greg Corrado, Wei Chai, Mustafa Ispir, al. Wide & deep learning for recom- mender systems. Proceedings of the 1st workshop on deep learning for recommender systems, pp. 7-10, 2016.
10

---

Published as a conference paper at ICLR 2026
Wei Chu, Lihong Li, Lev Reyzin, and Robert Schapire. Contextual bandits with linear payoff fune- tions. In International Conference on Artificial Intelligence and Statistics (AISTATS-II), pp- 2011.
Gregory Farquhar, Laura Gustafson, Zeming Lin, Shimon Whiteson, Nicolas Usunier, and Gabriel Synnaeve. Growing action spaces. In International Conference Machine Leurning, pp. 3040- 3051. PMLR, 2020.
Dimitris Fotakis. On the competitive ratio for online facility location. Algorithmica, 50(1):1-57, 2008.
Xiangyu Guo, Janardhan Kulkamni, Shi Li, and Jiayi Xian. the facility location problem in online and dynamic models. In Approximation, Randomization, and Combinatorial Optimization. Algo- rithms and Techniques (APPROX/RANDOM 2020), pp. 42-1. Schloss Seasstull-Libbii-Zeenee für Informatik, 2020.
Xiangnan He, Lizi Liao, Hanwang Zhang, Liqiang Nie, Xia Hu, and Tat-Seng Chua. Neural col- laborative filtering. In Proceedings of the 26th international conference on world wide web, pp. 173-182, 2017.
Sheng-Jun Huang, Rong Jin, and Zhi-Hua Zhou Active learning by querying informative and representative examples. Advances in neural information processing systems, 23, 2010.
Nicole Immorlica, Karthik Abinav Sankararaman, Robert Schapire, and Aleksandrs Slivkins. Ad- versarial bandits with knapsacks. In Annual Symposium on Foundations of Computer Science (FOCS-19), pp. 202-219. IEEE, 2019.
Chi Jin, Praneeth Netrapalli, Rong Ge, Sham M Kakade, and Michael I Jordan. A short note on concentration inequalities for random vectors with subgaussian norm. arXiv preprint arXiv:1902.037366 2019.
Haim Kaplan, David Naori, and Danny Raz. Almost tight bounds for online facility location in the random-order model. In Proceedings of the 2023 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). pp. 1523-1544. SIAM, 2023.
Tze Leung Lai and Herbert Robbins. Asymptotically efficient adaptive allocation rules. Advances in applied mathematics, 6(1):4-22, 1985.
Hoyeop Lee, Jinbae Im, Seongwon Jang, Hyunsouk Cho, and Sehee Chung. Melu: Meta-learned user preference estimator for cold-start recommendation. In Proceedings of the 25th ACM SIGKDD international conference on knowledge discovery & data mining, pp. 1073-1082, 2019.
Lihong Li, Wei Chu, John Langford, and Robert Schapire. A contextual- approach to personalized news article recommendation. In Proceedings of the 19th international conference on World wide web, pp. 661-670, 2010.
Shang Liu, Jiashuo Jiang, and Xiaocheng Li. Non-stationary bandits with knapsacks. Advances in Neural Information Processing Systems, 35: 16522-16532, 2022.
Ying Liu, Brent Logan, Ning Liu, Zhiyuan Xu, Jian Tang, and Yangzhi Wang. Deep reinforcement learning for dynamic treatment regimes medical registry data. In 2017 IEEE international conference on healthcare informatics (ICHI), pp. 380-385. IEEE, 2017.
Adam Meyerson. Online facility location. In Proceedings 42nd IEEE Symposium on Foundations of Computer Science, pp. 426-431. IEEE, 2001.
Jan A Van Mieghem and Nils Rudi. Newsvendor networks: Inventory management and capacity investment with discretionary activities. Manufacturing Service Operations Management, (4):313-335, 2002.
Michael Moor, Oishi Banerjee, Zahra Shakeri Hossein Abad, Harlan M Krumholz, Jure Leskovec, Eric Topol, and Pranav Rajpurkar. Foundation models for generalist medical artificial intelli- gence. Nature, 616(7956):259 265, 2023.
11

---

Published as a conference paper at ICLR 2026
Pranav Rajpurkar, Emma Chen, Oishi Banerjee, and Eric Topol. Ai in health and medicine. Nature medicine, 28(1):31-38, 2022.
Burr Settles, Active learning literature survey. 2009.
H Sebastian Seung, Manfred Opper, and Haim Sompolinsky. Query by committee. In Proceedings of the fifth annual workshop on Computational learning theory, pp. 287-294, 1992.
Aleksandrs Slivkins al. Introduction to multi-armed bandits. Foundations and Trends@ in Ma- chine Learning, 12(1-2):1-286 2019.
Paul Laszlo Zador. Development and evaluation of procedures for quantizing multivariate distribu- fions. Stanford University, 1964.
12

---

Published as a conference paper at ICLR 2026
Appendix
Statement of LLM Usage. We used large language models to assist with (1) text generation, composition, and language polishing, (2) drafting and revising Python code for algorithmic imple- mentations, and (3) literature search in broader fields. All scientific ideas, methodological choices, theoretical analysis and experimental design were conceived, implemented, and validated by the authors, and we have reviewed and verified all LLM-assisted content.
A
MORE DISCUSSIONS
In this section, we further discuss few fields and topics of research that are related to our problem modeling, motivation, methodology and implementation.
A.1 MORE RELATED WORKS
Online Learning with Resource Constraints. Another line of related research studies resource- limited bandits, such as "bandits with knapsack (BwK)" (Badanidiyuru al. 2013) and its versions (Agrawal & Devanur (016)] Immorlica et al. 2019 Liu et 2022).. In these scenarios, each arm- pulling consumes some portion of a finite resource (e.g.. budget, time, or capacity), and the algorithm aims to optimize the cumulative reward before resources run out. However, these approaches cannot be directly applied our problem because of key difference in resource consumption patterns. In BwK, resource consumption only affects the current period's secision-making In contrast, our setting involves a one-tine time cost for creating new arms that provides benefits across all future periods through expansion of the action space.
Digital Healthcare and Clinical Decision Support Digital healthcare and clinical decision sup- port systems (CDSS) represent rapidly evolving field where Al-powered systems must continu- ously balance the utilization of established medical knowledge with the creation of novel, patient- specific treatment protocols. Foundational work by Rajjuurkar al. (2022) on diagnostic AI systems and the comprehensive framework established by Moor et al. (2023) demonstrate how modern med- ical Al systems expand beyond narrow, single-task applications to flexible models capable of diverse medical reasoning tasks. Reinforcement learning approaches in critical care, particularly the system- atic review by Liu al. (2017) covering 21 RL applications intensive care units, illustrate how these systems extend from discrete medication dosing decisions to continuous, multi-dimeensionl treatment optimization spaces. The create-to-reuse paradigm is particularly evident in precision medicine applications, where systems invest computational resources in developing personalized treatment protocols that can subsequently be applied to patients with similar phenotypic character- istics, effectively creating reusable clinical knowledge that scales across patient populations while maintaining individualized care quality.
Recommendation Systems and Personalization Recommendation systems research has evolved from static collaborative filtering approaches to sophisticated frameworks that dynamically balance the exploitation of existing user preferences with the creation new personalized recommendation strategies. Neural Collaborative Filtering by HH al. (217)) and the Wide & Deep Learning frame- work by|Cheng et al. (016) established the foundation for deep learning approaches that can capture complex user-item interactions beyond traditional matrix factorization methods. Meta-learning ap- proaches, particularly Lee et al. (2019) demonstrate how recommendation systems can treat each user as a distinct learning task, creating personalized model parameters that generalize across dif- ferent applications and contexts. It is worth mentioning that the multi-armed bandit approaches in recommendation systems (Li al. 2010)) naturally embody the tradeoff's by continuously balancing known user preferences with the discovery of new content types and recommendation strategies. Our create-to-reuse framework directly parallels these systems' core functionality: recommendation systems routinely invest computational resources in creating personalized embeddings, meta-learned initialization parameters, and graph neural network repre- sentations that serve as reusable templates for rapid adaptation to users, items, and interaction modalities, while continuously expanding their action spaces through dynamic catalog growth and emerging user behavior patterns.
exploitation-crealee
13

---

Published as a conference paper at ICLR 2026
Active Learning Active learning frameworks fundamentally embody the exploration- apploitation-creation paradigm by allowing algorithms to strategically choose their training data, thereby naturally connecting sequential decision-making with expanding action spaces. Settles (2009) established the theoretical foundations for query selection strategies, while mem- bership query synthesis approaches (Angluin 1988) demonstrated how active learners create entirely new query types rather than merely selecting from existing unlabeled data pools. Query- by-Committee methods (Seung et al. (992) and extended through frameworks like QUIRE by Huang et al. (2010) show how multiple learning strategies can be combined to create adaptive query selection policies that balance informativeness and representativeness. Closer work on meta-active active learning and the "Growing Action Spaces" framework by Farquhar et al. (2020) directly address expanding action spaces through curriculum learning approaches that progressively grow query complexity. The create-to-reuse framework maps directly onto active learning's 's core mechanisms: systems invest computational effort in synthesizing new query types, developing committee-bar strategies, and learning meta-policies for query selection, creating reusable query generation mechanisms and adaptive selection strategies that can be applied across different datasets, domains, and learning tasks, while continuously expanding their query capabilities as they encounter new data distributions and learning scenarios.
Inventory Management Inventory management and supply chain systems represent a mature op- erations research domain where organizations continuously face fundamental tradeoff's between op- timizing existing supply chain capabilities and investing in new suppliers, products, or distribution channels. [ellmaan (1958) established the mathematical foundations of inventory theory, while dy- namic capacity expansion models (Mieghem & Rudi 2002) demonstrate how firms balance existing capacity utilization with flexible resource investments that create new operational capabilities. The create-to-reuss framework aligns naturally with supply chain ppcision-making organizations invest upfront in new suppliers, products, or distribution capabilities that become reusable assets for future deployment across different demand scenarios.
A.2 POTENTIAL EXTENSION AND GENERALIZATION
Dynamic and Context- Deeeedet Creation Costs. Our current framework assumes fixed cre- ation cost e across all time steps and contexts. natural extension would allow time-varying costs o, or context-dependent costs c(x;) that reflect realistic scenarios where creation difficulty varies with problem complexity or resource availability. This generalization would better capture applications like drug discovery, where synthesis costs depend molecular complexity, content generation, where review costs vary with topic sensitivity. However, this extension introduces significant algo- rithmic challenges, as evidenced by the substantially worse competitive ratios in variant-cost online facility location problems, where even achieving constant competitive ratios becomes impossible under adversarial sequences.
Non-Parametric and Neural Function Approximation. While theoretical analysis focuses on parametric quadratic loss functions d(æ, f)) our empirical experiments demonstrate promising re- sults when replacing the distance function with neural networks and using L.MMass--jjude for feed- back evaluation. Extending the theoretical guarantees to broader function classes, particularly neural networks kernel methods, would significantly broaden the applicability of our framework. The key challenge lies in controlling the complexity of the function class while maintaining meaning- ful regret bounds, potentially requiring techniques from neural tangent kernels (NTK) or Bayesian optimization (BO) to handle the high-dimensiona hypothesis space.
Scalability and Long-Term Operation. The algorithm presented in the main paper requires, at each time step I, search over the entire library existing contexts S, to find the one that minimizes the Lower Confidence Bound (LCB). A critical consideration for practical deployment in long- running systems is the scalability of this step as the library size [S,] grows.
1.
To empirically characterize the growth of the library, we ran simulations and recorded [.S.] with respect f. The results displayed in Figure We observe that in high-dimensional embedding spaces, |S,] tends to grow almost linearly with t. This is because the expected number of generated actions are O(T 24ズ x O(T)) as d being very large. Intuitively, new
14

---

Published as a conference paper at ICLR 2026
Library Growth Over Time
Library Size vs Cost
C-2:01
C-0:25
10000
110000
8000
C-1.00
8000
C=5.00
60
6000
(mec posoile
Library
C-10.00 00
0000
00
(9800=11
Final
4000
2000
2000
4000
6000
8000
10000
12000
30"2
10tt
307
101
Time Horizon
Cost Parameter
Figure 3: Library growth dynamics under varying creation costs c. (Left) The action library size |S,] grows slightly sub-linearly with time (below the dashed slope- line), with growth rate decreasing as t increases. (Right) The creation cost parameter e critically controls the creation- higher leads to substantially fewer library elements (blue) and lower generation rates (green), as the algorithm favors reusing existing actions despite greater mismatch loss. Error bars show standard deviation across runs.
tradeoff:
context in high dimensions F, frequently far from all existing library items f e S₁, making the creation of a new item more likely than reuse.
2. Our experiments show that the creation cost is the most significant hyperparameter for con- trolling library size. As seen in Figure 3] higher values of с substantially slow the growth of [Se]. as the algorithm is more heavily penalized for creating new items and is thus incen- tivized to tolerate a higher modeling loss from reusing an existing item. This provides a direct and practical lever for system designers to manage the trade-off between computational cost and the richness of the action library.
The potential for linear growth in [S, necessitates strategies to manage computational complexity. While the naive O[Sr, search is feasible for moderate T, large-scale systems would benefit from the following practical optimizations.
1. Approximate Nearest-Neighbor (ANN) Search:
The core of the selection step is to find arg mim ses, LCB(x,, f). The LCB is a function of the learned distance d(Ir, f) = (xx (TTW(x; - f)- This implies that the minimizing f is very likely to be one of the nearest neighbors to I; under this learned distance norm defined by W (an estimate of W). Instead of an exhaustive linear scan, we can use established ANN libraries to retrieve the nearest neighbors of 2; from S, in sublinear time (often O S.()). The LCB computation can then be restricted to this small candidate set. This optimization becomes increasingly reliable as the learned matrix W converges to a good representation of the underlying task structure.
2. Library De-activation and Caching: The theoretical result that an optimal covering of the context space has sublinear size of (dT4(()+)) suggests that if [S.] grows linearly, the library must contain a high degree of redundancy. This insight motivates a "de-activation" or caching strategy.
(i) We can maintain an "active set" of library items, which is subset of the full library St. At each step, the LCB computation is only performed over this active set.
(ii) The active set could managed using heuristics such as Least Recently Used (LRU), where items that have not been selected for long time are moved to inactive state. More sophisticated methods could periodically re-compute a core-set or a sparse covering of the full library S, to form the active set, ensuring that the entire space of created items is still represented. This approach contains the per-step computational cost while preserving the full library for long-term knowledge retention, aligning the practical implementation with the theoretical sublinear nature of the optimal solution.
Additional Baseline: LinLCB. We implemented a LinLCB baseline (a version of LinUCB (Chu et al. 2011) in terms of our loss-minimization setting) to select the best existing action, paired with
15

---

Published as a conference paper at ICLR 2026
Generation vs Mismatching Trade-offs
Normalized cumulative miametch los
1.0-
Our method 95% C
0.8
Status quo (no custom generation)
New generation every time
LinLCB baseline
0.6
Fixed-P baseline
0.4-
0.0
0.0
0.2
0.6
0.8
1.0
Fraction resporses
Figure 4: Comparison of creation-reuse strategies the Medical Q&A dataset. The LinLCB base- line (using LCB both for action selection and creation threshold) performs worse than our doubly- optimistic method and frequently falls above (worse than) the Fixed-P baseline. This degradation stems from a coupling effect: conservative LCB-based creation decisions suppress early library growth, which reduces exploration capacity and compounds into negative feedback loop of insuf- ficient learning and higher mismatch loss.
deterministic creation rule that creates iff miny (C (which is different from the creation cost c) to plot the generation-misman tradeoff curve as did in Section 6.2 This numerical experiment is conducted the Medical Q&A dataset, and we compare the performance of LinLCB against our method (doubly-optimistic) and the Fixed-P baseline. The results are shown in Figure
f] d, and we swept the threshold
Empirically, this LinLCB baseline performs worse than our method, and it even goes above (worse than) the Fixed-P baseline frequently. The main reason is a coupling effect: using an LCB both to select among existing actions and to trigger creation makes creation excessively conservative in early rounds (I. CBC are low under high uncertainty). This suppresses the addition new actions, which in turn limits future exploration capacity and compounds the problem-leading to fewer candidates and higher mismatch later. end up getting a negative feedback loop:
Optimism LinLCB lowers the best available LCB.
(ii) This suppresses the creation of new, necessary library items.
(iii) The library S; remains small and insufficient, leading to poor learning and high modeling error in the long run.
In contrast, the "Fixed-P" baseline, while naive, ensures constant and stable rate of library growth, preventing this collapse into a state of insufficient learning. This result highlights the critical dif- ference between "exploration" versus "creation" that might be misunderstood intuitively. To this extent, our "doubly-optimistic" framework does not just optimistically evaluate existing actions; it optimistically evaluates choice to create a new action by treating & as its potential value.
B PROOF DETAILS
Here we extend the proof sketch of Theorem 5.4 provided in Section 5 According to the roadmap depicted, to validate Theorem [54] we only need to prove the following Lemmas B. B.3 and B.8 We first propose the lemma that bounds OPT,
Lemma B.1 (OPT, upper bound). We have OPT, = O
Proof sketch. We propose context set (library) such that c |S| + ΣT min d(r,, Of d=t). Specifically, we let Š = N2, Naj IN E [ 1,2.... d} as 4- covering the context space of [0, 1]d. On the one hand, the cumulative mismatch loss due
16

---

Published as a conference paper at ICLR 2026
discretization of the context space is O(T 44d). On the other hand, the total cost of adding new contexts to the set is O(( )"( Let T 44a d' ata and the total loss is a d ). Please
kindly find a detailed proof in Appendix B.I
Before getting into the main lemma that upper bounds ALG, we present another lemma showing the concentration of d, (xt, f) within (x)
Lemma B.2 (A, estimation error). The estimation error of [d. (ri, f] d( f)] upper bounded by (x( d(x,, f) S de (2x, f) S d(r,, (Tt,,
f) with high probability. As consequence, we have (2 f) 21, S (
The proof of Lemma B.2 is deferred to Appendix B.2
In the following, we state the lemma that upper bounds the algorithmic loss by a constant competitive ratio over OPT, adding estimation errors. According
Lemma B.3 (Constant competitive ratio). We have ALG < 60OPT, + 54 (r(
Proof. Before starting the proof, we emphasize that all operations we make in this proof are made in the context space. As frequently mention in this paper, the actions only accessible through the oracle A(x) for some context z. Therefore, the context library S, is sometimes referred as "set" without causing misunderstandings.
First all, we note that the following two {a series have identical joint distributions:
(a) Sample sequence of Z1, 22, independently from an identical distribution Dx- (iid)
(b) Sample set of Z : {a1, 22,,22,..... 2T) independently from the identical distribution Dx, and then sample {xt}²=1 as uniformly random permutation of Z, i.c. {o1) ~ (Z)). Here ar (Z) denotes the permutation set of Z. (iid permutation)
Given this property, we assume that 3D = { 121,22,...1 22....,, JT}; ~ Dx {atT ~ U(o(Z)). In the following, we will keep using the notations of {at)emi and Z accordingly.
lid
Consider the optimal offline solution S such that
OPT, c (11, ..... FT +
Σ
min d(r,, fes-
(9)
c. =c-1S (21 22,.... 2T)
min d(sr; f). eES-
Here we denote S* (zi, #2,.... IT) and S* ..,... 2T) differently show that the offline solution is not dependent on the permutation, with slight abuse of notation. Denote S* =; For each c minjes- d(Ir. f) d(x,,c) c,), Vx, E C. In other words, C; consists of all x, 's that are assigned to of in the optimal solution St. Denote A = Et.ecc d(ze, ct) as the total optimal cost associated
(cf .g......ckl
1,2.... K, denote subset of {2t} as C such that
with of and a
as the average cost in C; |िन
Ai
Now, we define C.² and C as separated GOOD and BAD subsets of C;, respectively, such that
C¹ CO c c Cr, |C = Ic = | d(zg, cf) <d(as, cf), Vr, 2b E C².
2
(10)
In other words, C¹ and C represent the nearest half and the farthest half of x; 's in the set C;, in terms of distance to of. Note that the C and C are determined by Z and not relevant the permutation. Therefore, once Z is realized, the random sequence {x))²² does affect C and C+.
17

---

Published as a conference paper at ICLR 2026
Given these notations, present and prove the following two lemmas: a Lemma B.4 bounding the total loss of GOOD 2ι 's, and a Lemma B.6 bounding the individual loss each BAD 2ς
Lemma B.4. The total loss caused by all xt E C upper bounded as
Elll 3c 44; +4
Σ myECt
d(z o)) + Σ A (z fc).
(11)
tay
Proof of Lemma B.4 Denote the context set (library) sequence {St) Also, denote 4, (1( ft) and di == d(I,, cf for simplicity. In fact, any E C falls in one of the following two cases:
(I) When 3 ey E Sr such that d(e;, cf) & 2a;, we further categorize xy into three sub-cases:
L(a). At time select context e; and deploy at A(e;;) (i.c., 2t is matched to context
e,). We have
daa, ex) < 2(d(x),))) + (()) s 2( + 2a²).
(12)
The first inequality is due
1 d(a.b) + d(b,c) 2 ( vll.cc)
(13)
as a quadratic form. Hence
B[LeHaeee S 2d(x)) et) + 24(x,, fi) S 4(d; + 2a²) 2
(14)
I.b). At time i, e E Sz but at # A(ei), i.e. 24 matched to some other context ft even with the existence of e; Now we have
d(z,, fo) 24, & (x,, fi) dz,,,, ex) S d(x,, e.).
(15)
The second inequality comes from the arg-minimum definition of St, and the first and third inequalities is from Lemma B.2 Therefore, have
d(E,, fe) S de(ars ei) + 24. s ((d( + d(c), 24. 2(d; 2a;) 24,
(16)
Hence we have
ElIHH S 2d(2,, ex) 24, S 4(d) + 2a,) + 64.
(17)
I(C). e & S, at time f, i.e. Ie is matched to some ft before any close-enough context e; being added. In this case, propose the following lemma that provides overall loss bound for any group of [x,} J's, on which no new actions have been created.
Lemma B.5 (Constant loss bound before a new action being generated). Denote Q = {Ie, 1.2...., n/1 < t1 I ... I tn < T} subsequence of {xt) Also, de- note to as the first time in Q such that a new action is generated, i.e. at, A(x,,) and at * A(x,,),
We have
E
(18)
We defer the proof of Lemma B.5 A Appendix B.3
where will prove generalized claim. According to Lemma B.5 the total expected loss for all ig in this case can be bounded by c.
(II) When V Sq satisfies d(e, cf) > 2a,, know that new action are generated at time t, Vt D, E C.P Then we again apply Lemma B.5 and upper bound the expected total loss by
18

---

Published as a conference paper at ICLR 2026
Combining Case (a,b,c) and Case II, along with separate cost of adding e₁, have upper bound on the expected total loss for all t: 24 E C2 as follows:
E
Σ Bin E
Σ
+8
Σ
of
+
Σ
4
+
3c
time EO!
(19)
4
Σ
di +
4AA
+
+3c.
Here the last line comes from |
[cll
This proves Lemmal B.4
2
The previous lemma bounds the total loss GOOD xı 's while the following lemma will bound the individual loss of BAD s"
Lemma B.6. For each individual Tee E C. the expected loss is upper bounded as
2 < 4d(x), 4 fi)
2
(c+8
Σ S07
Σ d(z,,c)). (20)
|071
S:R, EC?
Proof sketch of Lemma B.6 Intuitively, later-arrived 's should be facing better situation as there are more action candidates. Therefore, for any 24 E C. if there exists a good point I, that emerges before the occurrence of zi, can upper bound E.4, with E[gg] adding d( c.). This is because we can at least match Fe to the existing in-library context that Tg was matched to. Denote /y as the existing context whose custom action 2g was assigned According to the "triangular inequality" shown as Equation (13) (up to constant coefficient), we have: E|4] S. O(d fg)) S. Odd(r, cf + d(c), fg)) S (d((a,, oj d(c) xgg) d((rg. fg)) = Odd(x,, < + d(Igg ct) + E(ty)). there no such a Hg (with very small probability), then we upper bound the expected loss by For detailed proof of Lemma [.6 please kindly refer Appendix B.4
Combining Lemma B.4
and Lemma B.6 above, have
E
Σ
4.
t: E Cf
=10 [
Σ
4 4|
4 E[ Σ
411
s:rr ECT
=E
4 (
+ E
21]
T.D,ECO
<T 4A7 +4
Σ
d(r,, G) +6
Σ
(x)ss
(21)
+ +E4
Σ
d(x,, G +4 Σ
(r,),
ECE
|
(c+8
Σ
BL. + 8 Σ
d(z,, c])]
2
< + 404; + 40 Σ
d(x of) +54
Σ
(xr,
ECO
<|E[2cc + 60.; + 54
Σ
4r fell
Here the last inequality is because Exxrecy d(z,, < Emireoy Emxrect A hand, the sum of losses in OPT, that are associated to oj equals + A. Therefore, we have ALG & 60OPT, 54 Et= (x ft). This ends the proof of Lemma B.3
On the other
2
n
19

---

Published as a conference paper at ICLR 2026
Remark B.7. The reason for us to divide {ar)'s 's into GOOD and BAD subsets is twofold.
(1)
We can upper-bound the total loss of all GOOD points, mainly because we have Lemma B.5 such that the Case I(c) and Case II hold. Lemma B.5 states that for any group of {x, ss the expected cost before new action being created (i.e. before new context is added to the library) among them is no more than c. Therefore, there does not exist an 6 close enough to c we know that no new actions have been created among GOOD {ar)'s (since any GOOD 2, satisfies dZ',, of) ) < 2a and therefore is qualified candidate e; once being added to the existing context library). However, this does not hold for BAD points, as they may still trigger new action generations although their contexts are faraway from c.
(2) We can only upper-bound the individual loss of each BAD Z2 due to the reason in (1) above. The individual upper bound for a BAD point is applicable for GOOD point, but this would introduce a linear dependence on T' - in the overall loss instead of constant ratio.
Now we propose the lemma where we upper bound the cumulative estimation error.
Lemma B.8 (Linear regression excess risk), The cumulative absolute ervor of online linear regres- sion with least least-square estimator satisfies Σ 4, = d(VdTT logT). T).
We defer the proof of Lemma B.8 to Appendix B.5 as a standard result from linear regression. According to what we stated earlier, this completes the proof of Theorem 5.4
In the following subsections, we present the proof details of lemmas proposed above.
B. PROOF OF LEMMA B.I
Proof. Let 5 = (1 N2...., Nal E 1 1,2...., .d. On the one hand, for any
text x [21, , 22
Fa] E Rd | & consider Due to the definition of S, we know that fa S. Also we have d(x, fz) = | fa <
[1 A, 2 4, ..... 4 A}.
|||4, ......,]]IIR & (max((W) ddd. On the other hand, we have |$| = (1) jd. Denote 5 as the solution to OPT, (as defined in Equation 9
we have
ОРT, =c 18
min d(xr,) J) fe
$c.
Σ
min d(r f) SES
1=1
(22)
Se.
1
)d
d( fzi)
1
<o( d +T Amax
A2d
1
0 4 + TT4'd)
and we let A = T alz d' ziz to make the RHS = O ddfz) dafz). This proves the lemma.
B.2 PROOF OF LEMMA
Proof. Here we prove
general result ridge regression:
Lemma B.9. Let I2,.,,,, In E Rd are d-dimension vectors, and yı := x, 0" + N,, where 8" E Rd is a fixed unknown vector such that | I ,and N₂ is a martingale difference sequence subject to a-subGaussia distributions. Denote X [21, .......,,, x,," E Raxd and
[/,, V/, ....... yn] E RR Let the ridge regression estimator
i = (xT X -xx
20

---

Published as a conference paper at ICLR 2026
where La is the d x d identity matrix. Then with probability Pr 2 1 - 6, we have
log( )) ( (XT Ia)-' x
50 1x - (1
(23)
holds for any 5 > and x E Rdd
Proof of Lemma B.9 Denote N == N
No E R" as the vector of noises in the labels.
Then we have
i -= x (a) X (x N.
(24)
Therefore, the difference between l" and & can be characterized as
o 0-- - - X XO- - (X X xx) N + + 1s)00 - -xXT + -a) XO (a)
= =(XTX + -a)" X + -X
=(XTX (0"
(0" NJ.
(25)
As result, we have
x T (0* 0)] = 1 (x x + 1 - X
(26)
< |1x x + 10 x TxxT(x X x
For the simplicity of notation, denote A [X + Ta)_1 1, then have 1x (0" 0) 1
| T AB + ||x" AX TX.. On the one hand, for the first term we have
T A0"
S
||A x/|2- |01||2
x T AAT x
(27)
S Vx Ar.
The second line is because ||0*|| s 1, and the last inequality is because A = A = (X xx + Ta)-1 x Ia-
On the other hand, for the second term, recall that we set A = (X + Ia) and g" = A (0 - x NN) We consider the random variable x AX N = Ei= N,, where the deterministic coefficients a, :- (x Ax),, 1=
Notice that {N₂) is martingale difference sequence with subGaussian tails. According to Ji et al. (2019 Proposition 7), which subGaussian version of Azuma Hooma---ffddig's Inequality, let and there exists constant J' such that
a Σ
n
2
N, SC,
log a
(28)
with probability Pr 2 1 8. Here ||a|1. = Σn af
x
TAXTXA
Ax S TT A because
X < x la-
Therefore, with probability at least 8,
AXTN| N| S &Cy
Ar log
(29)
Returning to TxT (6* 0)1 $ AA8 + |TAXTN already established (using
Ax. |10*12 < 1) that |x A0 < VΛ. Combining this with Equation (9 as the
martingale tail bound, we get |or T( 0)1 s Ax + Cy A log (2) =
(1 (1+C,, C, / log (2) VxT(XTX - -1x.
21

---

Published as a conference paper at ICLR 2026
This ends the proof of Lemma B.9
Now let us go back the proof of Lemma B.2 We apply this lemma for 67 times: in the proof of Lemma B.4 as Case I(a), I(b), I(c) (or Lemma 5.6) and II, and in the proof of Lemma B.6 as Case I and Case II, in each of which we adopt this concentration bound for each existing context f S
which is at most Therefore, we let + कर and let a (1 (1+
log 1272 8
||]|
According Lemma B.9 prove that d(ær, J) ( J) d( J) S d(r f) (1,,, f) holds for any f E St and Vt = 1,2..... T, with probability Pr 2 1 - 8. Therefore, we have proved Lemma
B.3 PROOF LEMMA B.5
Proof. Notice that at each time tx. with probability Pr (ocy we terminate this stochastic process, and with the Pr = de (ar we add de, (Ie S(x) our cumulative expected loss. Since di, (Teys fea) 2 de (Itz fw,, wk E [ni], we may instead prove a generalized version of this lemma.
P where E 10, 1]. The initial sum S O. At each time k with probability pk: we stop this stochastic process, otherwise we add pi to the sum S. We show that [[SS] < 1.
Lemma B.10. Consider an infinite sequence {PL, (pI.P2.... PP......PP.......
Lemma B.10 is a generalization of Lemma B.5 since we add deg (Iiy Stc) S dey (Fee Sia) at each time & in the latter setting.
Denote random variable Ls follows: 4 1 if the stochastic process has not stopped by the end of time k, and 1 = 0 otherwise. the case when 4 = 1, we add ps to the sum S. Therefore, we have
E =
Ph l
km
Also, we know that the probability that 4s = 1 is Pr(4y = 1] II (1-p.). As a result, we have
E[S = E
Pk Is]
k=1
(30)
8
Σ
Pk
p.).
k=1
In the following, show that Σ Pk II
1== (1 p.) S We first consider pk E (0, 1). Denote
Qo := 1 and Qx : Pr = I -= (1 -p), and we know Q& = (1 PPp) S Qk-1-
Also, we have P& Q (1
pk)]Q Qu-1- Qk.
For the rigorousness of the proof, we first show that Σ P4Qu is finite. Denote
T
PcQu.
(31)
and we have
T, <
Ph Q
k=1
Σ
Qk-1 Q
(32)
k=1
-Q0 Qn
<Qo
22

---

Published as a conference paper at ICLR 2026
As T, and Tn Tu, Vn 2 1, we have
lim T, S
(33)
n-
according the Monotone Convergence Theorem. Then slightly generalize the results above from Pk E (0, 1) to Ph E 00, I. i.e. incorporating and 1. In fact, if pt: = O, then we may skip this Qs term. Otherwise if pk 1, consider the first s.t. Pm 1, and then still have
-m1 Pk l Tm 1 and I IM for any M 2 m, M Z
Therefore, we have
[
Σ PkQu
k=1
Ps Qk-1
k=1
(34)
Qk-1
Qk
=Qo-
lim Qx
k000
S1.
This ends the proof of Lemma B.10 and therefore proves Lemma B.5
B.4 PROOF OF LEMMA B.6
Proof. Consider the moment when E C. arrives, and denote as the most recent moment (s t) such that Fg E C. According to the uniform permutation assumption from to {2,)T-> this wa can be any 2 E C with equal probability as Pr I the expected loss E[4] by cases:
2 In the following, we analyze |c
(I) xG E C. does exist before I, occurs. Denote ft = arg min,es, d(ct,)) f) as the closest context to og existed by the time t. Then we have:
f().
d(z,, ft) (1 de(
Eb (2:))
c <di(ar, fi) + d(zr,
<di(an, fi) + 2A, de( fe) + 22.
(35)
<2d, 1 +4d.
<2d(zr, fi) + 4A,
<4d(xe, (() )+ + 4d(c), St) + 44,
Also, denote f. := arg min ses. d(z,, f) as the best existing context that can be matched to 2e by the time s. Then we know that
Ea d(z,,f))
2 d(c fa) d(x,,c)) cf)
(36)
2 2 (() - (f)-
Combining Equation (35) with Equation 33 we have
E44 [ < 4d(Ie, cf) + 44, 4 2(B([. + d(z,,c)))
< 4d + 24. + 8 |C
Σ
BLI(A)T + d:).
(37)
Again, the last line of Equation 37 comes from the i.i.d. assumption of
23

---

Published as a conference paper at ICLR 2026
(II) If Fe E C does not exist before aa occurs, ie. 2, Cr t- According to 2
the uniform permutation from Z to {ai)== this event happens with probability [िा In
this case, if de( ft) c, then we suffer cost and we either generate a new action (with cost c) or suffer an expected loss at d( ft) _ (I Jt) < In nutshell, the expected loss does not exceed c.
time otherwise de fi) c,
Combining with Case I and Case Il above, we immediately get Equation 20
B.5 PROOF OF LEMMA B.8
Proof. Denote 4, (z fe) for simplicity. In the following, first reduce the summation of estimation error 4, to the regret a K(< -)aar linear bandit problem, up to constant factors. In fact, according to Lemma B.2 we know that d(zi, S de(x.. I d(zr, Since we select ft = arg mis, dz, f), we have
d(zi, fi) - 24, Sd(z1: - 24
<d((z1;
(38)
<de(sr, Si)
<d(ae,
fes, f( as the best existing context for x in the current context library at time t. Therefore, the performance gap between ft and f; can be bounded as d(x2, d(x fi S 24, On the other hand, since d(x,,, fr) =< w, (z fa) >> is a linear loss function, consider ((x,,) as the "context" of each arm f E St, and then we form a linear contextual bandit problem
where f := arg minses,
setting. Recall that 4 = a o( fi) Σ p(2,, ft). According to Chu et al. (2011) Lemma (which originates from Auer 2002) Lemma 13), we have
T
4
Σ a Vole, ET
(39)
S 5v (d 1 log M++1
S 5a / logT. log..
Here the second line is because the dimension of contexts are de as Φ( f) Vec((x: - f) T)T) E IRdd and the third line comes from the original definition of Vr as subset of [1. 1].
B.6 PROOF OF LOWER BOUND (THEOREM 5.5
Proof. In order to prove the lower bound, we show the following facts
1. OPT, = 22(Tatz) according to the K (eeeeeessne)ghhoooskkk)))))) lower bound.
2. Any online facility location algorithm suffers at least (2 com))-compeiiivveeaaio,,, i.e.
ALG 2 (2 - PI))
In the following, we present two lemmas corresponding to the facts above.
Lemma B.11 (OPT, lower bound). We have OPT Z OPT. ((T
Proof. Denote OPT.(K) = mins: |S| + E (aainses(EE,,))) K T
ming + ΣT minses d(z,, f). This equals T' times K n--narrsttneiihborss (K-NN) loss plus K. According to Zador (1964) (i.e. Zador's ' Theorem in coding theory), the mean squared distance
Herr we denote this covariate the context as it serves environmental description in the contextual bandits. We denote E Sz, which was denoted context the library, an of this contextual bandits.
24

---

Published as a conference paper at ICLR 2026
to the nearest codebook center in R$ space in Lorm is lower bounded by Q(K-ă). This is di- rectly applicable to K-NN which effectively partitions points by their nearest neighbors. Hence, the quantization lower bound established by Zador's ' Theorem translates into lower bound on K-NN's average squared loss. Therefore, we let r to fit in our setting, and then have
OPT.
min OPT.(K) (ec K + T K 3) ((( KE[T]
(40)
where the last line is an application of Hölder's Incquality that K + T K 2 K 1 (T
K i4 T and the equality holds at K T
). Let A be an algorithm for online facility location in the ii.dd model, then, the competitive ratio of A is at least 2 - o(1).
Lemma B.12 (Theorem 5.1 in Kaplan et al. (2023)).
Combining Lemma B.11 and Lemma B.12 we know that REG = ALG OPT. 2 (2 o(1) 1)OPT, 2 0.50PT, (((442)) This proves Theorem 5.5
C THE CONFIDENCE BOUND OF NEURAL NETWORK FOR REGRESSION
In our real-world numerical experiments conducted in Section 6.2 we use a neural network to re- place the linear regression estimator (i.e. the estimate of W matrix) in the learning task on the Medical Q&& Dataset. In order to use the same framework as demonstrated in Algorithm I we wish to not only obtain point predictions but also the confidence bound of predictions. In this section, we derive a general approach to achieve this quantification of NN output uncertainties.
Denote fx(x) the neural network and the output prediction. One way achieve this is by approximating the posterior distribution of the parameters with a Gaussian distribution (a Laplace approximation), leveraging the fact that under Gaussian prior and Gaussian likelihood, the result- ing posterior can be treated via approximate conjugacy.
Posterior approximation using Laplace: Assume that we place isotropic Gaussian prior on the parameters:
p() A(@0 0, sT)),
(41)
and model the observations with Gaussian noise:
ply x, 0)
NNy [o(x), o²1).
(42)
By defining L(0) log D), the Laplace approximation fits a Gaussian around the MAP Hessian approximation by
solution 0MPP. Denoting the
a Volemar (x4) Velerar (x:)
V L(ŌMAP)
I+ σ
(43)
obtain the approximate posterior
e D = N(OMAD: Σ)
where Σ - [(hAA)))))))
(44)
Confidence bound on fx): Since 0 is approximately Gaussian-distributee, a first-order (Delta- method) linearization gives
fo(x) ~ Soxar (x) + Volenar (x) (0 -0MAP).
(45)
Hence, the variance is:
Var[So(x)] 2 Volemer (x) E Voléran (x))
(46)
25

---

Published as a conference paper at ICLR 2026
Online update via Sherman-Morrison: When data arrives sequentially, maintain and update the Hessian approximation (or its inverse) via a rank-1 update procedure:
A. 2
(x) Vofa(x;)
(47)
52
r²
and
A411 = Ag + σ²
Vola (x
Volo(xx+1))
(48)
Using the Sherman-Morison formula, the inverse A
can be efficiently computed in ((d)):
- + A 1
g
AT
where
gr41
Voff((x++1)
(49)
0z B
A, ge+1
Thus, at any point time, we can maintain an approximate posterior inverse Hessian and readily compute confidence bound on (x) by plugging A," into the variance formula above.
26


Reviews:
[{"review_id": "JIdnq6htak", "reviewer": "Reviewer_uKET", "summary": "This paper introduces an online decision-making problem relevant to modern generative AI systems, where an agent can dynamically expand its action set. At each time step, the agent observes a context $x_t$ and faces a choice: (1) select an existing action $f$ from its library $S_t$ and incur a mismatch loss $d(x_t, f)$, or (2) pay a fixed cost $c$ to generate a new, context-specific action $\\mathcal{A}(x_t)$ which provides zero mismatch loss and is then permanently added to the library $S_{t+1}$. This frames a novel \"create-to-reuse\" problem, which the authors identify as a triangular trade-off among exploitation, exploration, and creation.\n\nTo solve this, the authors propose a **Doubly-Optimistic Algorithm**. This algorithm first identifies the best *existing* action $f_t$ by using a Lower Confidence Bound (LCB) on the mismatch loss (balancing exploitation and exploration). It then makes a stochastic decision on whether to *create* a new action based on the Upper Confidence Bound (UCB) of $f_t$'s loss, $\\hat{d}_t(x_t, f_t)$, opting to create with probability $\\min(1, \\hat{d}_t(x_t, f_t)/c)$.\n\nThe paper's main contributions are:\n1.  The \"create-to-reuse\" problem formulation.\n2.  The novel Doubly-Optimistic Algorithm.\n3.  A rigorous theoretical regret analysis, which assumes the loss $d(x,f)$ is an unknown quadratic function $d(x,f) = (x-f)^\\top W (x-f)$. The algorithm achieves an expected regret of $O(T^{\\frac{d}{d+2}}d^{\\frac{d}{d+2}} + d\\sqrt{T \\log T})$.\n4.  A matching information-theoretic lower bound of $\\Omega(T^{\\frac{d}{d+2}})$ (with respect to $T$), proving the algorithm's optimality.\n5.  Empirical validation on synthetic data (which verifies the theoretical regret rate) and on two real-world healthcare Q&A datasets (which demonstrates superior cost-quality trade-offs compared to a fixed-probability baseline).", "questions": "1.  **On the Theory-Practice Gap:** Could you elaborate on the theoretical guarantees for the simplified models used in the real-world experiments (the squared linear model and the neural network)? Does the $O(T^{\\frac{d}{d+2}})$ regret component (which seems related to the \"facility location\" aspect of the problem) still hold, even if the second regret term (from parameter estimation) changes from $O(d\\sqrt{T \\log T})$?\n2.  **On Scalability:** How did the algorithm's runtime scale empirically with $T$ and the library size $|S_t|$ in your Q&A experiments? The per-step complexity seems to be $O(|S_t| \\cdot \\text{dim})$. Do you foresee scalability issues as $T$ becomes very large, and do you have recommendations for mitigating this (e.g., nearest-neighbor search, action pruning)?\n3.  **On Baselines:** Could you comment on how your algorithm might compare to a baseline that uses a standard contextual bandit (like LinUCB) to select from $S_t$, paired with a deterministic creation rule like: \"create a new action if and only if $\\min_{f \\in S_t} \\tilde{d}_t(x_t, f) > c$\"? This seems like a natural alternative, and I am curious why the stochastic UCB-based rule is preferable.\n4.  **On the Oracle:** The analysis assumes the creation oracle $\\mathcal{A}(x_t)$ is \"perfect\" and provides a zero-loss action. How do you think the problem and algorithm would need to change if the oracle was imperfect, i.e., generating a new action still incurred some unknown (but hopefully small) mismatch loss $l_t(\\text{new}) > 0$, in addition to the fixed cost $c$?", "limitations": "", "rating": 8, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "* **Novel and Timely Problem:** The \"create-to-reuse\" formulation is a significant and timely contribution. It accurately models a new challenge posed by generative AI, where high-quality, custom actions (like detailed Q&A responses) are now possible to create on-the-fly, but at a non-trivial cost. This is a valuable and natural extension of the classic contextual bandit framework.\n* **Elegant Algorithm Design:** The \"doubly-optimistic\" principle is an intuitive and elegant solution to the new exploration-exploitation-creation trade-off. Using an LCB for *action selection* (to manage uncertainty among *known* actions) while using a UCB-based probability for *action creation* (to optimistically value the benefit of creating a new action) is a clever method for decomposing the problem.\n* **Strong Theoretical Results:** The paper provides a complete and rigorous theoretical analysis. Deriving the $O(T^{\\frac{d}{d+2}}d^{\\frac{d}{d+2}} + d\\sqrt{T \\log T})$ regret bound is a strong technical achievement. Proving its optimality by establishing a matching $\\Omega(T^{\\frac{d}{d+2}})$ lower bound makes the theoretical contribution self-contained and highly significant.\n* **Solid Empirical Validation:** The experiments are well-designed and provide compelling support for the claims. The synthetic experiments directly validate the theoretical regret rate $\\frac{d}{d+2}$, which is excellent. The real-world experiments on healthcare Q&A datasets convincingly demonstrate the algorithm's practical utility, showing it achieves a superior Pareto frontier for the cost-vs-mismatch-loss trade-off compared to a sensible baseline.\n* **Clarity:** The paper is exceptionally well-written. The problem is motivated clearly with concrete examples, the formal problem setup is precise, and the algorithm's intuition is explained very well.", "weaknesses": "* **Gap Between Theory and Practical Implementation:** The strong theoretical guarantees (optimality, regret rate) are derived under the assumption of a quadratic loss $d(x,f) = (x-f)^\\top W (x-f)$. This model has $O(d^2)$ parameters and leads to an \"impractical\" $O(d^4)$ complexity per-step, as the authors note. Consequently, the real-world experiments use computationally cheaper models: a rank-1 (squared linear) model $(\\theta^\\top(x-f))^2$ or a neural network. This creates a disconnect, as the theoretical guarantees do not strictly apply to the models used in the high-dimensional, practical validation. While the empirical results are strong, the paper would be improved by discussing this limitation more directly.\n* **Scalability of the Action Library $S_t$:** The algorithm, as presented, requires computing the LCB for *every* existing context key $f \\in S_t$ at *each* time step $t$. In a long-running system, the library $S_t$ could grow very large, potentially approaching $O(T)$ in size. This implies a per-step complexity that scales at least linearly with $|S_t|$ (e.g., $O(|S_t| \\cdot D^2)$ for the NN model). The paper notes the *expected* number of created contexts is sublinear $O(T^{\\frac{d}{d+2}})$, but this is not a worst-case guarantee. The paper would benefit from a discussion on the practical scalability for very large $T$ and whether mitigation strategies (e.g., approximate nearest-neighbor search for $f_t$, pruning the library $S_t$) would be necessary.\n* **Baseline for Comparison:** The \"Fixed-P\" baseline is a reasonable \"naive\" strategy. However, it is arguably too simple. It decides to create *independently* of the context $x_t$, and when it reuses, it performs pure exploitation (picking the most similar context). A stronger baseline might involve running a standard contextual bandit algorithm (like LinUCB) on the *current* set $S_t$ (to intelligently explore/exploit *existing* actions) and pairing this with a more intelligent heuristic for creation (e.g., \"create if the LCB loss of the best existing action is still greater than $c$\"). Comparing against such a baseline would provide a clearer picture of the value added by the specific \"doubly-optimistic\" creation rule.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "cnbuIMUYDU", "reviewer": "Reviewer_WJ1K", "summary": "The paper presents a novel sequential decision-making problem, where a decision maker has to learn to either pick a previously known action (exploitation/exploration) or generate a new one by paying a fixed cost (creation). The authors provide the first (doubly-optimistic) algorithm to solve this problem that is shown to achieve sub-linear regret, under some assumptions on the loss incurred. Further, the authors evaluate the performance of their approach on both synthetic and realistic datasets.", "questions": "- How would you extend your algorithm to consider more complex notions of loss? For example, a probabilistic loss dependent on the action/context pair (e.g., efficacy of a treatment for a patient $x_t$).\n- Would the regret-proof strategy still work under time- or context-dependent creation costs $c$? How do you envision your strategy to change?", "limitations": "", "rating": 8, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "_(Disclaimer: this is not exactly my area of expertise. I skimmed through the appendices and proofs, but I did not check them too deeply.)_\n\nThe paper tackles an interesting and timely problem, which I believe has several interesting ramifications and implications for several human-AI decision-making scenarios. The paper is clear in its exposition, and all the relevant assumptions are duly explained and motivated. Furthermore, the related work is described comprehensively (both in the main text and appendix), enabling a clear contextualization of the paper's proposed method. Overall, I enjoyed reading it.", "weaknesses": "I do not see any fundamental weakness in this work, based on my limited expertise with multi-armed bandit settings. The paper is clear in explaining the weaknesses (e.g., assumptions) of the proposed approach. \n\nI can only comment that some assumption feels very synthetic. For example, the quadratic loss function $d(x_t, f_t)$, while justified for tractability, limits generality and may underrepresent practical similarity measures (e.g., cosine or kernel-based metrics). Further, context-dependent or stochastic creation costs would also be interesting. Looking at practical applications, I would expect to measure the efficacy (regret) of Algorithm 1 in solving a certain decision-making task (e.g., curing a patient). Your algorithm would be oblivious to the fact that a pre-registered question is wrong, or it does not work for a given context (the same reasoning applies to generated actions).", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "qdOnzZQjDy", "reviewer": "Reviewer_yeWb", "summary": "The authors of the paper propose a method of reusing annotated actions in an online decision making framework. Specifically, the authors propose an algorithm that takes into account the cost of adding an action with cost $c$ (annotated answer in an FAQ setting) into a context library $S_t$ over reusing an already existing action which, might lead a loss due to the sub-optimal nature of the already existing answer. To reduce the overall computational complexity, the For theoretical purposes to calculate the regret bounds , the loss is approximated as a weighted squared distance, though in the empirical results, they use a squared linear model or a neural network (NN). \n\nNotation: \n- Input context variable $x_t \\in \\mathbb{R}^d$ i.e. vector embedding for questions in FAQ setting\n- $S_t:= \\{x_t, a_t\\}$ is a context library of vetted FAQs that is stored as a hash map. \n- $d(x,f)$ is the distance function which models the loss.", "questions": "Questions: \n- Section 6.2 line 432: \"cost parameter $c$ from 0 to 100 for our algorithm ...\" : Can you explain why you do this sweep across? Also, what does this cost mean from an intuitive sense? How does this tie back into the the *total loss*\n- I might have also missed this, but could you explain how you estimate/train the distance function for both the datasets in section 6 i.e. the squared liner model and NN mentioned in section 4.", "limitations": "", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "Strengths: \n- The paper address an important aspect of a real world problem i.e. when does one need to annotate new data vs. use existing data. Given that data annotation is a fairly laborious and expensive process, this would be a prudent approach proposed by the authors. \n- The approach is fairly simple and approachable. The algorithm in Algorithm 1 was easy to understand along with the reasoning about it's time complexity (though I'm not too convinced about using NNs to help with that). The algorithm also makes sense in having a LCB and UCB defined for the overall loss from a theoretical sense, but I might see issues here of it being practical.", "weaknesses": "Weakness: \n- The use of a NN to approximate the distance function to reduce computational complexity seems a little counter intuitive. Typical NNs would be sufficiently large that it might render this moot. \n- There is no study on how the size of the context library might impact the algorithm (like a cold start problem). It would also be good to understand if this framework leads to long term stability of needing an oracle. \n- I did not fully evaluate the authors theoretical claims, but I think some of their empirical results are not very convincing. Its hard to gauge the performance of the algorithm from 2 real world datasets.\n- I also think that from a practical standpoint, it would be hard for practitioners to tie in the relation between the distance metric and cost (the notion of a *total loss*)", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "sgCjbju6mW", "reviewer": "Reviewer_pGC5", "summary": "This paper studies a new bandit framework where a decision maker receives at each round a context $x_t$, and decides whether to (i) pick an optimal action $\\mathcal{A}(f)$ corresponding to an already-seen context $f\\in S_t$, or (ii) incur a fixed cost $c>0$ and generate a new action $\\mathcal{A}(x_t)$ specifically tailored to $x_t$, which becomes available for future rounds. This problem is mainy motivated  by healthcare QA systems. The authors propose a doubly-optimist algorithm to  solve this problem, and derive an optimal-in-T upper bound on the regret incurred by their algorithm. They then run two sets of experiements: one exactly implements the algorithm in a small dimension synthetic data setup; the other implements an approximate version of the algorithm (where the distance is predicted linearly) one actual QA data.", "questions": "1) Is it possible to extend the analysis to the case where $W$ depends on the context $x_t$ ?\n2) Are there other motivations for the problem studied in this paper?", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "1) The paper is very-well written and pedagogical. The authors did a great job presenting their setting and algorithm in a simple and intuitive way, without sacrificing mathematical soundness. \n2) The setting is interesting and is well motivated from a practical point of view (healthcare QA)\n3) The theoretical analysis is complete, thanks to a lower-bound complements the upper-bound on the regret incurred by the introduced algorithm. The convergence rate is very slow (exponential dependence on the dimension, almost linear dependence on T for large d), however this has to do with the inherent difficulty of the problem (as suggested by the lower bound).", "weaknesses": "1) I am not entirely convinced by the way the loss incurred by the algorithm is modeled. Indeed, the paper assumes that the loss incurred at each round is given by a (noisy) distance generated by $W$ between the actual context $x_t$ and the context chosen to generate the action. This is a quite restrictive modelling. In particular I would expect W to depend on $x_t$, so the loss would be $(x_t - f)^\\top W(x_t) (x_t -f)$. Indeed, answering to a question $f$ instead of the actual $x_t$ is likely to be more harmful when the user asks about cancer than about superficial wound for instance. By the way, this formulation would naturally arise by considering the second order Taylor expansion of the excess risk $h(x_t, \\mathcal{A}(f)) - h(x_t, \\mathcal{A}(x_t))$ for some decision loss $h$.\n2) The authors implement the algorithm for which they derive guarantees only on a very toyish example, and use a simplified version on the actiual QA dataset. Altough I understand that the dependence on $d$ makes the cost of an actual implementation prohibitive, it is quite unfortunate not to have a demonstration of the effectiveness of the algorithm on actual data, and not to have a theoretical guarantee of the simplified algorithm used in practise.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "M6byc4ZqYM", "reviewer": "Reviewer_GG79", "summary": "This paper studies an online learning problem with an expanding action space, motivated by generative AI systems that can create new actions on demand at a cost. The authors introduce the create-to-reuse framework, in which an agent decides at each time step whether to select an existing action or pay a one-time cost to generate a new, reusable action.\nTo solve this problem, the authors propose a doubly-optimistic algorithm that employs Lower Confidence Bounds (LCB) for action selection among existing options, and Upper Confidence Bounds (UCB) for deciding whether to create new actions.\nThis approach is theoretically shown to achieve a sublinear regret bound of O\\left(T^{\\frac{d}{d+2}} d^{\\frac{d}{d+2}} + d \\sqrt{T \\log T}\\right),\nwhich matches an  Ω(T^{d/(d+2)}) lower bound—making it optimal with respect to the time horizon T.\nEmpirical validation includes both synthetic data (to confirm regret rates) and real healthcare question-answering datasets (to demonstrate tradeoffs between creation cost and response mismatch). The proposed algorithm consistently outperforms fixed-probability baselines in terms of total loss and generation-quality efficiency.", "questions": "1. How critical is the quadratic assumption on mismatch loss? Would kernelized or neural distance functions maintain similar regret behavior?\n\n2. Can the proposed framework handle context-dependent creation costs c(x_t)? How would this affect the theoretical analysis?\n\n3. Could approximate nearest neighbor search or library pruning reduce complexity while preserving regret guarantees?\n\n4. The create-to-reuse tradeoff resembles selective labeling. Could active learning techniques (e.g., expected information gain) enhance the creation policy?\n\n5. How would the method extend to stochastic or partially observable generation outcomes (as in LLM-based action creation)?", "limitations": "", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "1.  Introduces an important and timely extension of online decision-making- expanding the action space through generative capabilities.\n2.  The double-optimism principle (LCB for reuse, UCB for creation) is conceptually appealing and well-motivated by the underlying tradeoffs.\n3.  Provides nontrivial analysis, including tight regret bounds and a matching lower bound.\n4. The healthcare Q&A examples effectively illustrate the value of balancing creation cost with reuse benefits.\n5. Real-data results show meaningful gains and smooth generation-quality tradeoffs.", "weaknesses": "1. The algorithm’s  worst-case complexity O(d^4 T^2) is prohibitive for high-dimensional embeddings (e.g., large language model contexts).\n   The paper proposes approximate implementations (linear or neural variants) but does not provide theoretical guarantees for them.\n\n2.  The  quadratic loss model d(x,f) = (x-f)^\\top W(x-f) may not generalize to real semantic spaces.\n  \n3.  Evaluation focuses mainly on healthcare QA; additional domains (e.g., recommendation systems or dynamic pricing) would strengthen claims of generality.\n\n4.  The probabilistic decision rule for creation (based on ( UCB/c )) could be analyzed more thoroughly-what happens if the stochastic component is removed or tuned differently?\n\n5.  Links to active learning, bandits with knapsacks, and growing action spaces (Farquhar et al., 2020) are discussed in the appendix, but not deeply integrated into the main narrative.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Poster)