Online Decision Making with Generative Action Sets

## Abstract

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 tradeoffs compared to baseline strategies.
From theoretical perspectives, we prove that our algorithm achieves the optimal regret of O ​ ( T d d + 2 ​ d d d + 2 + d ​ T ​ log ⁡ T ) 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.

## 1 Introduction

Sequential decision-making problems involve agents repeatedly selecting actions from a candidate set to maximize cumulative reward. Traditional approaches assume a fixed set of available actions, focusing on the exploration-exploitation tradeoffs: balancing empirically high-reward actions (exploitation) against less-tested alternatives (exploration). However, advances in generative AI have introduced a 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 capabilities enabled by new actions. Consider the following motivating scenarios:

###### Example 1.1 (Healthcare Question-Answering Systems) .

AI-powered healthcare platforms must decide between reusing existing vetted responses from their FAQ libraries or investing in creating 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). However, once created and vetted, these responses become reusable assets. When a patient in a given region asks “What are healthy meals during pregnancy?”, the system faces 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 a finite set of ad templates for different user contexts. Over time, the platform observes new user segments and decides to 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 at no additional cost.

In both scenarios, the agent must decide at each time step whether to select an existing action or pay a one-time cost to instantiate a new action perfectly suited to the observed context. This introduces a novel *create-to-reuse* problem that goes beyond traditional exploration-exploitation tradeoffs.

###### Example 1.1 (Healthcare Question-Answering Systems) .

###### Example 1.2 (Personalized Advertisement) .

#### Problem Formulation (preview).

We study an online learning problem with an *expanding* action space. At each time $t$, the agent first observes a context $x_{t}$. 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 $x_{t}$ (without any excess loss), at a fixed one-time cost.

This formulation has two key features. First, step (b) is notable in that the agent generates a new action only through an oracle ${\mathcal{A}}(x_{t})$ that is prompted by the context $x_{t}$. The learning algorithm operates as a decision-making layer on 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 (learning about existing uncertain actions), and creation (generating a new action to satisfy immediate needs while enriching future capabilities). Additionally, we have no prior experience with potential new actions or unlimited freedom to generate arbitrary ones – each creation must be specifically tailored to the current context at a fixed cost.

#### Summary of Contributions

Our main contributions are fourfold:

- 1.
Problem Modeling: We establish a new problem formulation that allows for costly expansion of the action space in online learning, formalizing the create-to-reuse framework.
- 2.
Algorithmic Framework: We propose a *doubly-optimistic* algorithm that uses Lower Confidence 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 generation-quality tradeoffs compared to baselines. Our results show the method gracefully interpolates between pure reuse and always-create policies while maintaining superior performance.
- 4.
Optimal Regret Guarantees: Under a semi-parametric loss model, our algorithm achieves $O(T^{\frac{d}{d+2}}d^{\frac{d}{d+2}}+d\sqrt{T\log T})$ expected regret, where $T$ is the time horizon and $d$ is the dimension of covariates. We prove this rate is optimal by establishing a matching $\Omega(T^{\frac{d}{d+2}})$ information-theoretic lower bound.

#### Technical Novelty.

The crux of our approach is a double optimism principle, which resolves the unique challenge of balancing creation with exploration/exploitation. Among existing actions, we rely on their *LCB* comparisons to both exploit high-performing actions and continue exploring uncertain ones. When evaluating creation decisions, we compare the *UCB* loss of the best existing action against the fixed generative cost, triggering creation with appropriate probability. This double optimism perspective naturally maximizes the long-term value of new actions while tightly controlling worst-case regret.

#### Paper Organization.

The rest of this paper is organized as follows. We discuss related literature in [Section˜2](https://arxiv.org/html/2509.25777v1#S2), then present the rigorous problem setting in [Section˜3](https://arxiv.org/html/2509.25777v1#S3) along with the necessary assumptions. We propose our main algorithm in [Section˜4](https://arxiv.org/html/2509.25777v1#S4), analyze its theoretical performance in [Section˜5](https://arxiv.org/html/2509.25777v1#S5), and conduct numerical experiments to validate its real-world performance in [Section˜6](https://arxiv.org/html/2509.25777v1#S6).

## 2 Related Works

Here we discuss related literature on the most relevant topics in online decision making. Please refer to [Appendix˜A](https://arxiv.org/html/2509.25777v1#A1) for discussions on broader fields including active learning, digital healthcare, recommendation system, and inventory management.

Multi-Armed and Contextual Bandits. The multi-armed bandit (MAB) problem has been extensively studied since Lai and Robbins (1985). The classic framework (Auer et al., 2002; Agarwal et al., 2014), that a decision-maker repeatedly selects from a 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. (2019) for a comprehensive discussion.

Online Facility Location.
Online facility location (OFL), studied by Meyerson (2001), Fotakis (2008), and Guo et al. (2020), is closely related to our formulation. In OFL, algorithms decide whether to open new facilities or assign requests to existing ones, minimizing facility costs plus assignment distances. While structurally similar to our problem, there are crucial differences. First, OFL assumes *known* distance metrics, while we must learn *unknown* parameters defining distances. Second, OFL *automatically* assigns points to nearest facilities, while we must *actively* select actions under uncertainty. Therefore, OFL involves a *two-way* trade-offs between immediate costs and future benefits, whereas our problem requires a *three-way* balance between exploitation, exploration, and creation, necessitating our novel algorithmic approach.

Online Learning with Resource Constraints. Another line of related research studies resource-limited bandits, such as “bandits with knapsack (BwK)” (Badanidiyuru et al., 2013) and its versions (Agrawal and Devanur, 2016; Immorlica et al., 2019; Liu et al., 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 to our problem because of a key difference in resource consumption patterns. In BwK, resource consumption only affects the current period’s decision-making. In contrast, our setting involves a one-time cost for creating new arms that provides benefits across all future periods through expansion of the action space. Besides, BwK mostly assumes a *hard* constraint on budgets, while we adopt a *soft* constraint as an additional cost in our problem setting.

## 3 Problem Setup

We now formalize the problem of creating-to-reuse as an online decision-making framework. In order to demonstrate the problem setting, we start with the healthcare Q&A scenario described in Example [1.1](https://arxiv.org/html/2509.25777v1#S1.Thmtheorem1). As an abstraction, each arriving patient question is represented as a $d$-dimensional *context* vector $x_{t}$ in a learned semantic embedding space.
The system maintains a context library $S_{t}$ of vetted FAQ entries, implemented as a *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 $\mathcal{A}(\cdot)$. Crucially, the algorithm operates only in the context representation space by searching through context keys in $S_{t}$. When a new question $x_{t}$ arrives, the algorithm makes decisions based on estimated losses and can either:

- (a)
Decide to create a new custom response by paying a fixed cost $c$ and adding context $x_{t}$ as a new key to the library. The generation oracle $\mathcal{A}(\cdot)$ then automatically produces the tailored action $a_{t}=\mathcal{A}(x_{t})$, and the pair $(x_{t},a_{t})$ becomes permanently available for future reuse. *Or*
- (b)
Select an existing context key $f\in S_{t}$ from the library. The system automatically retrieves the corresponding action $a_{t}=S_{t}(f)=\mathcal{A}(f)$ and deploys it for context $x_{t}$, incurring a mismatch loss $d(x_{t},f)$ that reflects the difference between (1) the custom response to context $x_{t}$ versus (2) the action tailored for another context $f$.

Technically, we consider the following problem setting.

Initialization: Context-to-action oracle ${\mathcal{A}}(\cdot)$. A library $S_{1}=\{f,\mathcal{A}(f)\}$ with context keys $f$ and vetted custom actions $\mathcal{A}(f)$.
For $t=1,2,...,T:$
1.
Observe $x_{t}\in\mathbb{R}^{d}$ (patient question arrives).
2.
The algorithm decides whether to create a customized response to $x_{t}$. If YES, then
(i)
Generation oracle produces and deploys $a_{t}=\mathcal{A}(x_{t})$ (custom response to $x_{t}$).
(ii)
Receive a fixed loss $c$ (creation cost).
(iii)
Update $S_{t+1}:=S_{t}\cup\{x_{t}:a_{t}\}$ (add new context-action pair to the library).
3.
If NO, then
(i)
Select an existing context key $f_{t}\in S_{t}$ and retrieve $a_{t}=S_{t}(f_{t})$.
(ii)
Receive a loss $l_{t}:=d(x_{t},f_{t})+N_{t}$ (noisy mismatch penalty).
(iii)
Update $S_{t+1}:=S_{t}$ (library unchanged).

In this formulation, $d(x_{t},f_{t})$ captures the expected mismatch loss when deploying an action originally designed for context $f_{t}$ to serve context $x_{t}$. While this fundamentally reflects the difference between ${\mathcal{A}}(x_{t})$ and ${\mathcal{A}}(f_{t})$ in the action space, the algorithm can only estimate this through context-space relationships since it lacks direct access to ${\mathcal{A}}(x_{t})$ (actions having not been generated yet).

For theoretical analysis, our main modeling assumption is that this mismatch can 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(x,f):=(x-f)^{\top}W(x-f)$ (1) $$

where $W\in\mathbb{S}_{+}^{d}$ is an unknown positive semi-definite $d\times d$ matrix. Accordingly, denote

$$ $\displaystyle w=$ $\displaystyle Vec(W)\in\mathbb{R}^{d^{2}}$ (2) $\displaystyle\phi(x,f)=$ $\displaystyle Vec[(x-f)(x-f)^{\top}]\in\mathbb{R}^{d^{2}},$ $$

and we have an equivalent definition as $d(x,f):=\phi(x,f)^{\top}w$.

Why we assume a quadratic parametric loss? The motivation is that contexts are embedded in a 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(x_{t},x_{t})=0$, our formulation measures the excess cost due to not generating a custom action for each $x_{t}$. This fits scenarios where the algorithm interacts with complex action spaces through oracle $\mathcal{A}(x_{t})$ (human expert or generative model); our aim is to achieve good performance relative to this oracle’s capabilities. Modeling $d(\cdot,\cdot)$ as a squared distance function captures more structure than linear parametric choices while remaining more tractable than nonparametric formulations. Furthermore, the empirical results our algorithm performs on real-world Healthcare 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](https://arxiv.org/html/2509.25777v1#S5).

###### Assumption 3.1 (Quadratic parametric loss) .

## 4 Algorithm

To solve this online decision-making problem with expanding context libraries, we propose a “Doubly-Optimistic” algorithm. This section presents the algorithm design and highlights its properties. We will analyze and bound its cumulative regret in the next section.

Figure: Algorithm 1 Doubly-Optimistic Algorithm

The pseudocode of our algorithm is displayed in [Algorithm˜1](https://arxiv.org/html/2509.25777v1#alg1). At each time $t$, the algorithm inherits loss estimation parameters $\Sigma_{t-1}$, $b_{t-1}$ (^1^11Linear regression parameters. We estimate the vector $w$ as $\Sigma_{t-1}^{-1}b_{t-1}$ at every time step $t$.) and context library $S_{t}$ from $(t-1)$, then observes a new context vector $x_{t}$. Using the estimation parameters, it computes predicted mismatch loss $\bar{d}_{t}(x_{t},f)$ and uncertainty bound $\Delta_{t}(x_{t},f)$ for each existing context key $f\in S_{t}$. The algorithm operates entirely in the context representation space and takes the following two steps to determine which action to deploy.

- (i)
Lower Confidence Bound (LCB) loss on existing contexts. For each existing context key $f$, we calculate the LCB loss as $\check{d}_{t}(x_{t},f)=\bar{d}_{t}(x_{t},f)-\Delta_{t}(x_{t},f)$. We then select $f_{t}$ 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 a new entry. After identifying $f_{t}$ as the best existing option, we turn to consider its UCB loss $\hat{d}_{t}(x_{t},f_{t})=\bar{d}_{t}(x_{t},f_{t})+\Delta_{t}(x_{t},f_{t})$ and compare it against the fixed creation cost $c$. With a probability of $\min\{1,\frac{\hat{d}_{t}(x_{t},f_{t})}{c}\}$, we decide to create a new entry: The oracle generates $a_{t}={\mathcal{A}}(x_{t})$ and we add context $x_{t}$ to the library. Otherwise, we reuse the existing context $f_{t}$, and the system retrieves $a_{t}=S_{t}[f_{t}]$ from library $S_{t}$. After receiving a mismatching loss $l_{t}$, the algorithm update the estimation parameters $\Sigma_{t}$ and $b_{t}$ accordingly.

As the argmin of LCB loss, $f_{t}$ represents the existing context that could potentially yield the lowest mismatch under optimistic assumptions, balancing exploration and exploitation given historical uncertainties. This approach aligns with contextual bandit methods such as Chu et al. (2011).

The UCB-based creation probability $\frac{\hat{d}_{t}(x_{t},f_{t})}{c}$ increases the chance of adding new contexts when the estimated mismatching loss is high relative to creation cost (within a risk $\Delta_{t}$ we can tolerate). This design enables us 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 in [Lemma˜B.5](https://arxiv.org/html/2509.25777v1#A2.Thmtheorem5).

#### Computational Complexity

[Algorithm˜1](https://arxiv.org/html/2509.25777v1#alg1) incurs worst-case time complexity $O(d^{4}T^{2})$, as it compute matrix-vector products of $d^{2}$ dimension for every context key $f\in S_{t}$ at each round $t$, with at most $T$ contexts possible. Since the expected number of newly created contexts is $O(T^{\frac{d}{d+2}})$ with respect to $T$, the *expected* complexity refines to $O(T^{\frac{2d+2}{d+2}})$.
Given that $d$ can represent sentence embedding dimensions in the Q&A scenario, an $O(d^{4})$ time complexity is impractical. In our real-data numerical experiments, we improve computational performance by replacing the estimated distance function $\bar{d}_{t}(x,f)$ with either of the two forms:

- (a)
A squared linear model $(\theta^{\top}(x-f))^{2}$ (equivalent to setting $W=\theta\theta^{\top}$), reducing the computational complexity to $O(d^{2})$. Uncertainty bounds are derived from ridge regression covariance matrices.
- (b)
A neural network $d(x,f;\Theta)$ with uncertainty function $\Delta_{t}(x,f;\Theta)$ derived under Gaussian conjugate assumptions, reducing complexity to $O(D^{2})$ where $D:=\|\Theta\|_{0}$ is the number of NN parameters.

On the other hand, we implement the original algorithm in the synthetic-data simulations to validate the theoretic guarantees with respect to $T$ (for small $d$’s only).

## 5 Theoretical Analysis

In this section, we provide a regret analysis of our algorithm.
We first state the performance metric and necessary technical assumptions. Then we present the main theorem on the algorithmic regret upper bound. Finally, we provide a corresponding lower bound that matches the leading term of the upper bound with respect to $T$.

### 5.1 Definitions and Assumptions

As we have stated by the end of [Section˜3](https://arxiv.org/html/2509.25777v1#S3), our goal is to minimize the *total loss*. In order to measure the performance, we adopt the expected *regret* as the loss metric, which is defined as follows:

###### Definition 5.1 (Optimal and Regret) .

Denote the minimal expected loss(^2^22Expectation taken over observation noises only. Same for the definition of $OPT_{o}$.) that is *achievable* in hindsight as $OPT_{h}$, which equals:

$$ $\displaystyle OPT_{h}=\min_{{\mathcal{S}}:=\{S_{1},S_{2},\ldots,S_{T},S_{T+1}|S_{t+1}\setminus S_{t}\subseteq\{x_{t}\}\}}c\cdot|S_{T+1}|+\sum_{t=1}^{T}\min_{f\in S_{t+1}}d(x_{t},f).$ (5) $$

There also exists a *non-achievable* minimal loss denoted as $OPT_{o}$, which is only accessible by an omniscient oracle that knows $\{x_{t}\}_{t=1}^{T}$ and selects an optimal option set ahead of time:

$$ $\displaystyle OPT_{o}=\min_{S}c\cdot|S|+\sum_{t=1}^{T}\min_{f\in S}d(x_{t},f).$ (6) $$

From the definition, we know that $OPT_{o}\leq OPT_{h}$. Also, denote the expected loss obtained by our algorithm as $ALG$, which equals:

$$ $\displaystyle ALG=c\cdot|S_{T+1}|+\sum_{t=1}^{T}\min_{f\in S_{t+1}}d(x_{t},f).$ (7) $$

Define the regret $REG$ as the expected loss difference(^3^33Expectation taken over the $\{x_{t}\}_{t=1}^{T}$ series.) between $OPT_{h}$ and $ALG$.

$$ $\displaystyle REG=\mathbb{E}[ALG-OPT_{h}]$ (8) $$

We then make two distributional assumptions on the covariates and the noises, respectively.

###### Assumption 5.2 (Covariate distribution and norm bound) .

Assume $x_{t}\in\mathbb{R}^{d},t=1,2,\ldots,T$ are drawn from independent and identical distributions (i.i.d.), with $d\geq 2$. Also, assume a norm bound as $\|x_{t}\|_{2}\leq 1$.

Assumption [5.2](https://arxiv.org/html/2509.25777v1#S5.Thmtheorem2) is necessary for us to effectively learn the metric matrix $W$ through online linear regression. For the same reason, we assume a subGaussian noise on the observations as follows:

###### Assumption 5.3 (Noise distribution) .

Assume that $N_{t}\in\mathbb{R},t=1,2,\ldots,T$ are drawn from *$\sigma$-subGaussian i.i.d.*, where $\sigma$ is a universal constant.

###### Definition 5.1 (Optimal and Regret) .

###### Assumption 5.2 (Covariate distribution and norm bound) .

###### Assumption 5.3 (Noise distribution) .

### 5.2 Regret Bounds

In this subsection, we 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](https://arxiv.org/html/2509.25777v1#S5.SS1), the expected regret of our [Algorithm˜1](https://arxiv.org/html/2509.25777v1#alg1) is upper bounded by $O(T^{\frac{d}{d+2}}d^{\frac{d}{d+2}}+d\sqrt{T\log T})$.

###### Proof Sketch.

We prove [Theorem˜5.4](https://arxiv.org/html/2509.25777v1#S5.Thmtheorem4) in the following sequence:

- 1.
([Lemma˜B.1](https://arxiv.org/html/2509.25777v1#A2.Thmtheorem1)) We upper bound the non-achievable minimal loss as $OPT_{o}=O(T^{\frac{d}{d+2}}d^{\frac{d}{d+2}})$. This is proved by a fine-grid covering of the space.
- 2.
([Lemma˜B.3](https://arxiv.org/html/2509.25777v1#A2.Thmtheorem3)) We upper bound the algorithmic loss $ALG$ within a constant competitive ratio of $OPT_{o}$ adding cumulative prediction errors: $\mathbb{E}[ALG]=O(\mathbb{E}[OPT_{o}+\sum_{t=1}^{T}\Delta_{t}(x_{t},f_{t})])$. To prove this, we divide $\{x_{t}\}$’s into “good” and “bad” groups, and bound their excess loss respectively.
- 3.
([Lemma˜B.8](https://arxiv.org/html/2509.25777v1#A2.Thmtheorem8)) We upper bound the excess risk $\mathbb{E}[\sum_{t=1}^{T}\Delta_{t}(x_{t},f_{t})]=O(d\sqrt{T\log T})$ by standard online linear regression (similar to Chu et al. (2011) by replacing $d$ with $d^{2}$).
- 4.
Finally, we derive the regret upper bound as $REG=\mathbb{E}[ALG-OPT_{h}]=O(T^{\frac{d}{d+2}}d^{\frac{d}{d+2}}+d\sqrt{T\log T})$ according to the three steps above.

Please refer to [Appendix˜B](https://arxiv.org/html/2509.25777v1#A2) 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 an instance of problem setting presented in [Section˜3](https://arxiv.org/html/2509.25777v1#S3), such that the regret is at least $\Omega(T^{\frac{d}{d+2}})$ with respect to $T$ (despite the dependence on $d$).

We defer the proof to [Section˜B.6](https://arxiv.org/html/2509.25777v1#A2.SS6). The main idea is to apply the $\Omega(K^{-\frac{2}{d}})$ lower bound for the K-nearest-neighbors (K-NN) problem, along with an optimal choice of $K$ that balance this term with $c\cdot K$. [Theorem˜5.5](https://arxiv.org/html/2509.25777v1#S5.Thmtheorem5) indicates that our algorithm achieves an optimal regret with respect to $T$.

###### Theorem 5.4 (Regret upper bound) .

###### Proof Sketch.

###### Theorem 5.5 (Regret lower bound) .

## 6 Empirical Performance

In this section, we conduct numerical experiments to validate our method’s performance. We first run the original algorithm on low-dimensional synthetic data to demonstrate the regret dependence on $T$. Then we adapt our algorithm to real-world healthcare Q&A scenarios and show better tradeoffs between generation cost and mismatching loss compared to baselines.

### 6.1 Regret Validation on Synthetic Data

Figure: (a) $d=2$
Refer to caption: x1.png

We evaluate our doubly-optimistic algorithm on synthetic data with dimensions $d=2,3,4$ over time horizon $T=10,000$, repeated for $N=10$ epochs. Context vectors $x_{t}$ are drawn from $L_{2}$-normalized uniform distributions, with noise $N_{t}\sim{\mathcal{N}}(0,0.05)$. We calculate regret by comparing the algorithmic loss against $OPT_{o}$ (defined in [Equation˜6](https://arxiv.org/html/2509.25777v1#S5.E6)), approximated by randomized K-means++ with Lloyd iterations over potentially optimal values of $K$. We do not apply $OPT_{h}$ as its computational cost is exponentially dependent on $T$.

[Figure˜1](https://arxiv.org/html/2509.25777v1#S6.F1) presents the regret curves in log-log scale to reveal the power dependence of regret on $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 $\frac{d}{d+2}$ according to [Theorem˜5.4](https://arxiv.org/html/2509.25777v1#S5.Thmtheorem4). These results validate our theoretical analysis in synthetic environments.

Note: We restrict experiments to low-dimensional settings due to the computational cost of $OPT_{o}$ (a necessary component of regret) in high dimensions, where K-means++ becomes ineffective and the underlying nearest neighbor problem is NP-hard. Despite these computational limitations, the synthetic validation confirms that our approach achieves the predicted theoretical regret rates, providing confidence in its performance for moderate-dimensional real-world applications.

### 6.2 Generation-Quality Tradeoffs Analysis on Healthcare Q&A Datasets

Figure: (a) Numerical results on a maternal health Q&A dataset from Nivi.Inc.
Refer to caption: x4.png

We evaluate our algorithm on two real-world healthcare Q&A datasets to demonstrate its practical effectiveness:

- 1.
Nivi’s Maternal Health Dataset: A dataset containing 839 user queries, with 12 pre-written FAQs for pregnant women, provided by Nivi.Inc, a company that provides healthcare chatbot services on WhatsApp.
- 2.
Medical Q&A Dataset: A public collection of 47,457 medical question-answer pairs curated from 12 NIH websites ([https://www.kaggle.com/datasets/gvaldenebro/cancer-q-and-a-dataset](https://www.kaggle.com/datasets/gvaldenebro/cancer-q-and-a-dataset)).

#### Experimental Setup.

Our experimental framework models the create-to-reuse decision process operating entirely in the context representation space. All questions are mapped to embeddings using OpenAI’s pre-trained text-embedding-3-small model, creating a semantic representation space where the algorithm makes decisions. For each arriving question context $x_{t}$, the algorithm decides whether to select an existing context key $f$ from the FAQ library or add $x_{t}$ as a new context key and then invoke the custom answer generation oracle ${\mathcal{A}}(\cdot)$.

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&A 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 $x_{t}$ and an existing context $f$ in the FAQ library, the loss is calculated as $(1-\text{cosine similarity})$ between $x_{t}$’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 ${\mathcal{A}}(\cdot)$.

As we also mentioned in [Section˜4](https://arxiv.org/html/2509.25777v1#S4), to maintain computational tractability, we model the estimated loss function as $\bar{d}(x,f)=(\theta^{\top}(x-f))^{2}$ (on the maternal health dataset) or adopt a neural network $d(x,f;\Theta)$ (on Medical Q&A Dataset).

We evaluate our doubly-optimistic algorithm against a fixed-probability baseline strategy. This baseline makes i.i.d. Bernoulli decisions $\sim\text{Ber}(p)$ at each time step: with probability $p$, generate a custom response; otherwise, select the most similar existing context from the library based on cosine similarity between question embeddings (note that it has no access to the custom answer before generation). To comprehensively evaluate performance across different cost-accuracy preferences, we vary the probability parameter $p$ uniformly across $[0,1]$ for the baseline. Meanwhile, we also vary the creation cost parameter $c$ from 0 to $100$ for our algorithm, generating complete tradeoff curves for both approaches.

The numerical results are depicted in [Figure˜2](https://arxiv.org/html/2509.25777v1#S6.F2), where points and curves closer to the bottom-left indicate superior performance. We plot cumulative generation costs against cumulative mismatch losses, with both metrics normalized separately to $[0,1]$ scale for interpretability. Generation costs are normalized by the total cost of the always-generate strategy, while mismatch losses are normalized 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 Nivi ’s Maternal Health Dataset.

[Figure˜2(a)](https://arxiv.org/html/2509.25777v1#S6.F2.sf1) presents the generation-quality tradeoffs. Starting with 12 pre-written FAQs, our algorithm demonstrates several key advantages:

- 1.
Context Clustering: Compared with the always-generating strategy (green triangle), approximately 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.

[Figure˜2(b)](https://arxiv.org/html/2509.25777v1#S6.F2.sf2) presents results on the public 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-answer pairs from each category to create a generic response (a total of 32 FAQs).

Compared with the always-generating and FAQ-only baselines respectively, our algorithm can reduce 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, as 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 to the greater diversity in the Medical Q&A dataset, spanning 37 question types across 32 medical topics.
In contrast, Nivi’s dataset focuses specifically on maternal health with more concentrated topics and frequently recurring keywords, producing clearer semantic connections and stronger correlations between context and action similarities 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 Discussions

#### Dynamic and Context-Dependent Creation Costs.

Our current framework assumes a fixed creation cost $c$ across all time steps and contexts. A natural extension would allow time-varying costs $c_{t}$ or context-dependent costs $c(x_{t})$ 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 on molecular complexity, or content generation, where review costs vary with topic sensitivity. However, this extension introduces significant algorithmic 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 our theoretical analysis focuses on parametric quadratic loss functions $d(x,f)$, our empirical experiments demonstrate promising results when replacing the distance function with neural networks and using LLM-as-a-judge for feedback evaluation. Extending the theoretical guarantees to broader function classes, particularly neural networks or kernel methods, would significantly broaden the applicability of our framework. The key challenge lies in controlling the complexity of the function class while maintaining meaningful regret bounds, potentially requiring techniques from neural tangent kernels (NTK) or Bayesian optimization (BO) to handle the high-dimensional hypothesis space.

## 8 Conclusion

In this paper, we introduced an online decision-making 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 a doubly-optimistic algorithm that achieves $O(T^{\frac{d}{d+2}}d^{\frac{d}{d+2}}+d\sqrt{T\log T})$ regret. This regret rate was proved optimal with a matching lower bound, and was validated through simulations. We also implemented our algorithm on a real-world healthcare Q&A dataset to make decisions on generating new answers v.s. applying an FAQ. Our results open up new avenues for optimizing creation decisions in online learning, with potential extensions to broader loss models and flexible creation costs.

## Acknowledgments

This work is partially supported by the Engler Family Foundation and the NSF AI 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

- Agarwal et al. [2014]
Alekh Agarwal, Daniel Hsu, Satyen Kale, John Langford, Lihong Li, and Robert Schapire.
Taming the monster: A fast and simple algorithm for contextual bandits.
In *International Conference on Machine Learning (ICML-14)*, pages 1638–1646, 2014.
- Agrawal and Devanur [2016]
Shipra Agrawal and Nikhil Devanur.
Linear contextual bandits with knapsacks.
*Advances in neural information processing systems*, 29, 2016.
- Angluin [1988]
Dana Angluin.
Queries and concept learning.
*Machine learning*, 2(4):319–342, 1988.
- Auer [2002]
Peter Auer.
Using confidence bounds for exploitation-exploration trade-offs.
*Journal of Machine Learning Research*, 3(Nov):397–422, 2002.
- Auer et al. [2002]
Peter Auer, Nicolo Cesa-Bianchi, and Paul Fischer.
Finite-time analysis of the multiarmed bandit problem.
*Machine learning*, 47(2):235–256, 2002.
- Badanidiyuru et al. [2013]
Ashwinkumar Badanidiyuru, Robert Kleinberg, and Aleksandrs Slivkins.
Bandits with knapsacks.
In *Annual Symposium on Foundations of Computer Science (FOCS-13)*, pages 207–216. IEEE, 2013.
- Bellman [1958]
Richard Bellman.
Studies in the mathematical theory of inventory and production, 1958.
- Chen et al. [2019]
Boxiao Chen, Xiuli Chao, and Hyun-Soo Ahn.
Coordinating pricing and inventory replenishment with nonparametric demand learning.
*Operations Research*, 67(4):1035–1052, 2019.
- Cheng et al. [2016]
Heng-Tze Cheng, Levent Koc, Jeremiah Harmsen, Tal Shaked, Tushar Chandra, Hrishi Aradhye, Glen Anderson, Greg Corrado, Wei Chai, Mustafa Ispir, et al.
Wide & deep learning for recommender systems.
In *Proceedings of the 1st workshop on deep learning for recommender systems*, pages 7–10, 2016.
- Chu et al. [2011]
Wei Chu, Lihong Li, Lev Reyzin, and Robert Schapire.
Contextual bandits with linear payoff functions.
In *International Conference on Artificial Intelligence and Statistics (AISTATS-11)*, pages 208–214, 2011.
- Farquhar et al. [2020]
Gregory Farquhar, Laura Gustafson, Zeming Lin, Shimon Whiteson, Nicolas Usunier, and Gabriel Synnaeve.
Growing action spaces.
In *International Conference on Machine Learning*, pages 3040–3051. PMLR, 2020.
- Fotakis [2008]
Dimitris Fotakis.
On the competitive ratio for online facility location.
*Algorithmica*, 50(1):1–57, 2008.
- Guo et al. [2020]
Xiangyu Guo, Janardhan Kulkarni, Shi Li, and Jiayi Xian.
On the facility location problem in online and dynamic models.
In *Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2020)*, pages 42–1. Schloss Dagstuhl–Leibniz-Zentrum für Informatik, 2020.
- He et al. [2017]
Xiangnan He, Lizi Liao, Hanwang Zhang, Liqiang Nie, Xia Hu, and Tat-Seng Chua.
Neural collaborative filtering.
In *Proceedings of the 26th international conference on world wide web*, pages 173–182, 2017.
- Huang et al. [2010]
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.
- Immorlica et al. [2019]
Nicole Immorlica, Karthik Abinav Sankararaman, Robert Schapire, and Aleksandrs Slivkins.
Adversarial bandits with knapsacks.
In *Annual Symposium on Foundations of Computer Science (FOCS-19)*, pages 202–219. IEEE, 2019.
- Jin et al. [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.03736*, 2019.
- Kaplan et al. [2023]
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)*, pages 1523–1544. SIAM, 2023.
- Kothawade et al. [2022]
Suraj Kothawade, Shivang Chopra, Saikat Ghosh, and Rishabh Iyer.
Active data discovery: Mining unknown data using submodular information measures.
In *ICML workshop on Adaptive Experimental Design and Active Learning in the Real World*, 2022.
- Lai and Robbins [1985]
Tze Leung Lai and Herbert Robbins.
Asymptotically efficient adaptive allocation rules.
*Advances in applied mathematics*, 6(1):4–22, 1985.
- Lee et al. [2019]
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*, pages 1073–1082, 2019.
- Li et al. [2010]
Lihong Li, Wei Chu, John Langford, and Robert E Schapire.
A contextual-bandit approach to personalized news article recommendation.
In *Proceedings of the 19th international conference on World wide web*, pages 661–670, 2010.
- Liu et al. [2022]
Shang Liu, Jiashuo Jiang, and Xiaocheng Li.
Non-stationary bandits with knapsacks.
*Advances in Neural Information Processing Systems*, 35:16522–16532, 2022.
- Liu et al. [2017]
Ying Liu, Brent Logan, Ning Liu, Zhiyuan Xu, Jian Tang, and Yangzhi Wang.
Deep reinforcement learning for dynamic treatment regimes on medical registry data.
In *2017 IEEE international conference on healthcare informatics (ICHI)*, pages 380–385. IEEE, 2017.
- Meyerson [2001]
Adam Meyerson.
Online facility location.
In *Proceedings 42nd IEEE Symposium on Foundations of Computer Science*, pages 426–431. IEEE, 2001.
- Mieghem and Rudi [2002]
Jan A Van Mieghem and Nils Rudi.
Newsvendor networks: Inventory management and capacity investment with discretionary activities.
*Manufacturing & Service Operations Management*, 4(4):313–335, 2002.
- Moor et al. [2023]
Michael Moor, Oishi Banerjee, Zahra Shakeri Hossein Abad, Harlan M Krumholz, Jure Leskovec, Eric J Topol, and Pranav Rajpurkar.
Foundation models for generalist medical artificial intelligence.
*Nature*, 616(7956):259–265, 2023.
- Rajendran et al. [2023]
Prajit T Rajendran, Huascar Espinoza, Agnes Delaborde, and Chokri Mraidha.
Unsupervised unknown unknown detection in active learning.
In *The IJCAI-2023 AISafety and SafeRL Joint Workshop*, 2023.
- Rajpurkar et al. [2022]
Pranav Rajpurkar, Emma Chen, Oishi Banerjee, and Eric J Topol.
Ai in health and medicine.
*Nature medicine*, 28(1):31–38, 2022.
- Settles [2009]
Burr Settles.
Active learning literature survey.
2009.
- Seung et al. [1992]
H Sebastian Seung, Manfred Opper, and Haim Sompolinsky.
Query by committee.
In *Proceedings of the fifth annual workshop on Computational learning theory*, pages 287–294, 1992.
- Slivkins et al. [2019]
Aleksandrs Slivkins et al.
Introduction to multi-armed bandits.
*Foundations and Trends® in Machine Learning*, 12(1-2):1–286, 2019.
- Xu et al. [2025a]
Jianyu Xu, Xuan Wang, Yu-Xiang Wang, and Jiashuo Jiang.
Joint pricing and resource allocation: An optimal online-learning approach.
*arXiv preprint arXiv:2501.18049*, 2025a.
- Xu et al. [2025b]
Jianyu Xu, Yining Wang, Xi Chen, and Yu-Xiang Wang.
Dynamic pricing with adversarially-censored demands.
*arXiv preprint arXiv:2502.06168*, 2025b.
- Zador [1964]
Paul Laszlo Zador.
*Development and evaluation of procedures for quantizing multivariate distributions*.
Stanford University, 1964.
- Zhao et al. [2024]
Peng Zhao, Jia-Wei Shan, Yu-Jie Zhang, and Zhi-Hua Zhou.
Exploratory machine learning with unknown unknowns.
*Artificial Intelligence*, 327:104059, 2024.

## Appendix A More Discussions

In this section, we further discuss a few fields and topics of research that are related to our problem modeling, motivation, methodology and implementation.

#### Active Learning

Active learning frameworks fundamentally embody the exploration-exploitation-creation paradigm by allowing algorithms to strategically choose their training data, thereby naturally connecting to sequential decision-making with expanding action spaces. Settles [2009] established the theoretical foundations for query selection strategies, while membership query synthesis approaches [Angluin, 1988] demonstrated how active learners can create entirely new query types rather than merely selecting from existing unlabeled data pools. Query-by-Committee methods [Seung et al., 1992] 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 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 core mechanisms: systems invest computational effort in synthesizing new query types, developing committee-based 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.

#### Exploratory Learning for Unknown Unknowns.

Another notable progress is the exploratory machine learning (ExML) framework [Zhao et al., 2024]. The authors introduced a novel and insightful approach to address unexpected unknown unknowns by exploring additional feature information through environmental interactions within a budget constraint, where an optimal bandit identification strategy is proposed to guide the feature exploration. There are several follow-up developments [Kothawade et al., 2022, Rajendran et al., 2023]. Compared to our create-to-use framework, there are two main differences: On the one hand, their work addresses the strategic choices of “create” while the current exploratory decisions would not be “in use” of future decisions. On the other hand, their cost serves as a budget consumption instead of a tradeoffs with cumulative utilities, analogous to the divergence between regret minimization and best-arm identification.

#### Digital Healthcare and Clinical Decision Support

Digital healthcare and clinical decision support systems (CDSS) represent a rapidly evolving field where AI-powered systems must continuously balance the utilization of established medical knowledge with the creation of novel, patient-specific treatment protocols. Foundational work by Rajpurkar et al. [2022] on diagnostic AI systems and the comprehensive framework established by Moor et al. [2023] demonstrate how modern medical AI systems expand beyond narrow, single-task applications to flexible models capable of diverse medical reasoning tasks. Reinforcement learning approaches in critical care, particularly the systematic review by Liu et al. [2017] covering 21 RL applications in intensive care units, illustrate how these systems extend from discrete medication dosing decisions to continuous, multi-dimensional 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 characteristics, 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 of new personalized recommendation strategies. Neural Collaborative Filtering by He et al. [2017] and the Wide & Deep Learning framework by Cheng et al. [2016] established the foundation for deep learning approaches that can capture complex user-item interactions beyond traditional matrix factorization methods. Meta-learning approaches, particularly by Lee et al. [2019] demonstrate how recommendation systems can treat each user as a distinct learning task, creating personalized model parameters that generalize across different applications and contexts. It is worth mentioning that the multi-armed bandit approaches in recommendation systems [Li et al., 2010] naturally embody the exploration-exploitation-creation tradeoffs 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 representations that serve as reusable templates for rapid adaptation to new users, items, and interaction modalities, while continuously expanding their action spaces through dynamic catalog growth and emerging user behavior patterns.

#### Inventory Management

Inventory management and supply chain systems represent a mature operations research domain where organizations continuously face fundamental tradeoffs between optimizing existing supply chain capabilities and investing in new suppliers, products, or distribution channels. Bellman [1958] established the mathematical foundations of inventory theory, while dynamic capacity expansion models [Mieghem and Rudi, 2002] demonstrate how firms balance existing capacity utilization with flexible resource investments that create new operational capabilities. The problem of inventory management often coexists with revenue management [Chen et al., 2019], resource allocation [Xu et al., 2025a], and adversarial online learning [Xu et al., 2025b] that occurs frequently in modern supply chains. The create-to-reuse framework aligns naturally with supply chain decision-making: organizations invest upfront in new suppliers, products, or distribution capabilities that become reusable assets for future deployment across different demand scenarios.

## Appendix B Proof Details

Here we extend the proof sketch of [Theorem˜5.4](https://arxiv.org/html/2509.25777v1#S5.Thmtheorem4) provided in [Section˜5](https://arxiv.org/html/2509.25777v1#S5). According to the roadmap depicted, to validate [Theorem˜5.4](https://arxiv.org/html/2509.25777v1#S5.Thmtheorem4), we only need to prove the following [Lemmas˜B.1](https://arxiv.org/html/2509.25777v1#A2.Thmtheorem1), [B.3](https://arxiv.org/html/2509.25777v1#A2.Thmtheorem3) and [B.8](https://arxiv.org/html/2509.25777v1#A2.Thmtheorem8). We first propose the lemma that bounds $OPT_{o}$.

###### Lemma B.1 ( $OPT_{o}$ upper bound) .

We have $OPT_{o}=O(T^{\frac{d}{d+2}}d^{\frac{d}{d+2}})$.

###### Proof sketch.

We propose a context set (library) $\tilde{S}$ such that $c\cdot|\tilde{S}|+\sum_{t=1}^{T}\min_{f\in\tilde{S}}d(x_{t},f)=O(T^{\frac{d}{d+2}}d^{\frac{d}{d+2}})$. Specifically, we let $\tilde{S}:=\{[N_{1},N_{2},\ldots,N_{d}]^{\top}|N_{i}\in[\frac{1}{\Delta}],i=1,2,\ldots,d\}$ as a $\Delta$-covering set over the context space of $[0,1]^{d}$. On the one hand, the cumulative mismatch loss due to discretization of the context space is $O(T\cdot\Delta^{2}d)$. On the other hand, the total cost of adding new contexts to the set is $O((\frac{1}{\Delta})^{d})$. Let $\Delta=T^{-\frac{1}{d+2}}d^{-\frac{1}{d+2}}$ and the total loss is $O(T^{\frac{d}{d+2}}d^{\frac{d}{d+2}})$. Please kindly find a detailed proof in [Section˜B.1](https://arxiv.org/html/2509.25777v1#A2.SS1).
∎

Before getting into the main lemma that upper bounds $ALG$, we present another lemma showing the concentration of $\bar{d}_{t}(x_{t},f)$ within $\Delta_{t}(x_{t},f)$.

###### Lemma B.2 ( $\Delta_{t}$ as estimation error) .

The estimation error of $|\bar{d}_{t}(x_{t},f)-d(x_{t},f)|$ is upper bounded by $\Delta_{t}(x_{t},f)$ with high probability. As a consequence, we have $d(x_{t},f)-2\Delta_{t}(x_{t},f)\leq\check{d}_{t}(x_{t},f)\leq d(x_{t},f)\leq\hat{d}_{t}(x_{t},f)\leq d(x_{t},f)+2\Delta_{t}(x_{t},f)$.

The proof of [Lemma˜B.2](https://arxiv.org/html/2509.25777v1#A2.Thmtheorem2) is deferred to [Section˜B.2](https://arxiv.org/html/2509.25777v1#A2.SS2).
In the following, we state the lemma that upper bounds the algorithmic loss by a constant competitive ratio over $OPT_{o}$ adding estimation errors. According to

###### Lemma B.3 (Constant competitive ratio) .

We have $ALG\leq 60OPT_{o}+54\sum_{t=1}^{T}\Delta_{t}(x_{t},f_{t}).$

###### Proof.

Before starting the proof, we emphasize that all operations we make in this proof are made in the *context* space. As we frequently mention in this paper, the actions are only accessible through the oracle ${\mathcal{A}}(x)$ for some context $x$. Therefore, the context library $S_{t}$ is sometimes referred as a “set” without causing misunderstandings.

First of all, we note that the following two $\{x_{t}\}_{t=1}^{T}$ series have identical joint distributions:

- (a)
Sample a sequence of $x_{1},x_{2},\ldots,x_{T}$ independently from an identical distribution $\mathbb{D}_{X}$. (iid)
- (b)
Sample a set of $Z:=\{z_{1},z_{2},\ldots,z_{T}\}$ independently from the identical distribution $\mathbb{D}_{X}$, and then sample $\{x_{t}\}_{t=1}^{T}$ as a uniformly random permutation of $Z$, i.e. $\{x_{t}\}_{t=1}^{T}\sim U(\sigma(Z))$. Here $\sigma(Z)$ denotes the permutation set of $Z$. (iid + permutation)

Given this property, we assume that $\exists Z=\{z_{1},z_{2},\ldots,z_{T}\},z_{t}\overset{\text{i.i.d.}}{\sim}\mathbb{D}_{X},\{x_{t}\}_{t=1}^{T}\sim U(\sigma(Z))$.
In the following, we will keep using the notations of $\{x_{t}\}_{t=1}^{T}$ and $Z$ accordingly.

Consider the optimal offline solution $S^{*}$ such that

$$ $\displaystyle OPT_{o}$ $\displaystyle=c\cdot|S^{*}(x_{1},x_{2},\ldots,x_{T})|+\sum_{t=1}^{T}\min_{f\in S^{*}}d(x_{t},f)$ (9) $\displaystyle=c\cdot|S^{*}(z_{1},z_{2},\ldots,z_{T})|+\sum_{t=1}^{T}\min_{f\in S^{*}}d(x_{t},f).$ $$

Here we denote $S^{*}(x_{1},x_{2},\ldots,x_{T})$ and $S^{*}(z_{1},z_{2},\ldots,z_{T})$ differently to show that the offline solution is not dependent on the permutation, with slight abuse of notation. Denote $S^{*}=:\{c_{1}^{*},c_{2}^{*},\ldots,c_{K}^{*}\}$. For each $c_{i}^{*},i=1,2,\ldots,K$, denote a subset of $\{x_{t}\}$ as $C_{i}^{*}$ such that $\min_{f\in S^{*}}d(x_{t},f)=d(x_{t},c_{i}^{*}),\forall x_{t}\in C_{i}^{*}$. In other words, $C_{i}^{*}$ consists of all $x_{t}$’s that are assigned to $c_{i}^{*}$ in the optimal solution $S^{*}$. Denote $A_{i}^{*}:=\sum_{t:x_{t}\in C_{i}^{*}}d(x_{t},c_{i}^{*})$ as the total optimal cost associated with $c_{i}^{*}$, and $a_{i}^{*}:=\frac{A_{i}^{*}}{|C_{i}^{*}|}$ as the average cost in $C_{i}^{*}$.

Now, we define $C_{i}^{g}$ and $C_{i}^{b}$ as separated good and bad subsets of $C_{i}^{*}$, respectively, such that

$$ $\displaystyle C_{i}^{g}\subset$ $\displaystyle C_{i}^{*},\ C_{i}^{b}\subset C_{i}^{*},\ |C_{i}^{g}|=|C_{i}^{b}|=\frac{|C_{i}^{*}|}{2}$ (10) $\displaystyle d(x_{g},c_{i}^{*})\leq$ $\displaystyle d(x_{b},c_{i}^{*}),\forall x_{g}\in C_{i}^{g},x_{b}\in C_{i}^{b}.$ $$

In other words, $C_{i}^{g}$ and $C_{i}^{b}$ represent the nearest half and the farthest half of $x_{t}$’s in the set $C_{i}^{*}$, in terms of distance to $c_{i}^{*}$. Note that the sets $C_{i}^{g}$ and $C_{i}^{b}$ are determined by $Z$ and not relevant to the permutation. Therefore, once $Z$ is realized, the random sequence $\{x_{t}\}_{t=1}^{T}$ does not affect $C_{i}^{g}$ and $C_{i}^{b}$.

Given these notations, we present and prove the following two lemmas: a [Lemma˜B.4](https://arxiv.org/html/2509.25777v1#A2.Thmtheorem4) bounding the *total* loss of good $x_{t}$’s, and a [Lemma˜B.6](https://arxiv.org/html/2509.25777v1#A2.Thmtheorem6) bounding the *individual* loss of each bad $x_{t}$’s.

###### Lemma B.4 .

The total loss caused by all $x_{t}\in C_{i}^{g}$ is upper bounded as

$$ $\sum_{t:x_{t}\in C_{i}^{g}}\mathbb{E}[l_{t}|\{x_{t}\}_{t=1}^{T}]\leq 3c+4A_{i}^{*}+4\sum_{x_{t}\in C_{i}^{g}}d(x_{t},c_{i}^{*})+6\sum_{t=1}^{T}\Delta_{t}(x_{t},f_{t}).$ (11) $$

###### Proof of Lemma ˜ B.4 .

Denote the context set (library) sequence as $\{S_{t}\}_{t=1}^{T}$. Also, denote $\Delta_{t}:=\Delta_{t}(x_{t},f_{t})$ and $d_{t}^{*}:=d(x_{t},c_{i}^{*})$ for simplicity.
In fact, any $x_{t}\in C_{i}^{g}$ falls in one of the following two cases:

- (I)
When $\exists\ e_{i}\in S_{T}$ such that $d(e_{i},c_{i}^{*})\leq 2a_{i}^{*}$, we further categorize $x_{t}$ into three sub-cases:
I.(a). At time $t$, we select context $e_{i}$ and deploy $a_{t}={\mathcal{A}}(e_{i})$ (i.e., $x_{t}$ is matched to context $e_{i}$). We have
$\displaystyle d(x_{t},e_{i})\leq 2(d(x_{t},c_{i}^{*})+d(c_{i}^{*},e_{i}))\leq 2(d_{t}^{*}+2a_{i}^{*}).$
(12)
The first inequality is due to
$d(a,b)+d(b,c)\geq\frac{1}{2}d(a,c),\forall a,b,c\in\mathbb{R}^{d^{2}}.$
(13)
as a quadratic form. Hence
$\displaystyle\mathbb{E}[l_{t}|\{x_{t}\}_{t=1}^{T}]\leq 2d(x_{t},e_{i})+2\Delta(x_{t},f_{t})\leq 4(d_{t}^{*}+2a_{i}^{*})+2\Delta_{t}.$
(14)
I.(b). At time $t$, $e_{i}\in S_{t}$ but $a_{t}\neq{\mathcal{A}}(e_{i})$, i.e. $x_{t}$ is matched to some other context $f_{t}$ even with the existence of $e_{i}$. Now we have
$\displaystyle d(x_{t},f_{t})-2\Delta_{t}\leq\check{d}_{t}(x_{t},f_{t})\leq\check{d}_{t}(x_{t},e_{i})\leq d(x_{t},e_{i}).$
(15)
The second inequality comes from the arg-minimum definition of $f_{t}$, and the first and third inequalities is from [Lemma˜B.2](https://arxiv.org/html/2509.25777v1#A2.Thmtheorem2). Therefore, we have
$\displaystyle d(x_{t},f_{t})$
$\displaystyle\leq d_{t}(x_{t},e_{i})+2\Delta_{t}\leq 2(d(x_{t},c_{i}^{*})+d(c_{i}^{*},e_{i}))+2\Delta_{t}\leq 2(d_{t}^{*}+2a_{i}^{*})+2\Delta_{t}$
(16)
Hence we have
$\displaystyle\mathbb{E}[l_{t}|\{x_{t}\}_{t=1}^{T}]\leq 2d(x_{t},e_{i})+2\Delta_{t}\leq 4(d_{t}^{*}+2a_{i}^{*})+6\Delta_{t}.$
(17)
I.(c). $e_{i}\notin S_{t}$ at time $t$, i.e. $x_{t}$ is matched to some $f_{t}$ before any close-enough context $e_{i}$ being added. In this case, we propose the following lemma that provides an *overall* loss bound for any group of $\{x_{t}\}$’s, on which no new actions have been created.
Lemma B.5 (Constant loss bound before a new action being generated).
Denote $Q:=\{x_{t_{i}},\ i=1,2,\ldots,n|1\leq t_{1}\leq\ldots\leq t_{n}\leq T\}$ as a subsequence of $\{x_{t}\}_{t=1}^{T}$. Also, denote $t_{k}$ as the *first* time in $Q$ such that a new action is generated, i.e. $a_{t_{k}}={\mathcal{A}}(x_{t_{k}})$ and $a_{t_{i}}\neq{\mathcal{A}}(x_{t_{i}}),i\leq k-1$. We have
$\mathbb{E}[\sum_{i=1}^{k-1}l_{t_{i}}|\{x_{t}\}_{t=1}^{T}]\leq c.$
(18)
We defer the proof of [Lemma˜B.5](https://arxiv.org/html/2509.25777v1#A2.Thmtheorem5) to [Section˜B.3](https://arxiv.org/html/2509.25777v1#A2.SS3), where we will prove a generalized claim.
According to [Lemma˜B.5](https://arxiv.org/html/2509.25777v1#A2.Thmtheorem5), the total expected loss for all $x_{t}$ in this case can be bounded by $c$.
- (II)
When $\forall\ e\in S_{T}$ satisfies $d(e,c_{i}^{*})>2a_{i}^{*}$, we know that no new action are generated at time $t$, $\forall t:\ x_{t}\in C_{i}^{g}$. Then we again apply [Lemma˜B.5](https://arxiv.org/html/2509.25777v1#A2.Thmtheorem5) and upper bound the expected total loss by $c$.

Combining Case I (a,b,c) and Case II, along with a separate cost $c$ of adding $e_{i}$, we have an upper bound on the expected total loss for all $t:\ x_{t}\in C_{i}^{g}$ as follows:

$$ $\displaystyle\mathbb{E}[\sum_{t:x_{t}\in C_{i}^{g}}l_{t}]$ $\displaystyle\leq 4\sum_{t:x_{t}\in C_{i}^{g}}d_{t}^{*}+8\sum_{t:x_{t}\in C_{i}^{g}}a_{i}^{*}+6\sum_{t:x_{t}\in C_{i}^{g}}\Delta_{t}+3c$ (19) $\displaystyle=4\sum_{t:x_{t}\in C_{i}^{g}}d_{t}^{*}+4A_{i}^{*}+6\sum_{t:x_{t}\in C_{i}^{g}}+3c.$ $$

Here the last line comes from $|C_{i}^{g}|=\frac{|C_{i}^{*}|}{2}$. This proves [Lemma˜B.4](https://arxiv.org/html/2509.25777v1#A2.Thmtheorem4).
∎

The previous lemma bounds the *total* loss of good $x_{t}$’s, while the following lemma will bound the *individual* loss of bad $x_{t}$’s”.

###### Lemma B.6 .

For each individual $x_{t}\in C_{i}^{b}$, the expected loss is upper bounded as

$$ $\mathbb{E}[l_{t}|Z]\leq 4d(x_{t},c_{i}^{*})+4\Delta_{t}(x_{t},f_{t})+\frac{2}{|C_{i}^{*}|}\cdot(c+8\sum_{s:x_{s}\in C_{i}^{g}}\mathbb{E}[l_{s}|Z]+8\sum_{s:x_{s}\in C_{i}^{g}}d(x_{s},c_{i}^{*})).$ (20) $$

###### Proof sketch of Lemma ˜ B.6

Intuitively, *later*-arrived $x_{t}$’s should be facing a *better* situation as there are more action candidates. Therefore, for any $x_{t}\in C_{i}^{b}$, if there exists a good point $x_{g}$ that emerges before the occurrence of $x_{t}$, we can upper bound $\mathbb{E}[l_{t}]$ with $\mathbb{E}[l_{g}]$ adding $d(x_{t},c_{i}^{*})$. This is because we can at least match $x_{t}$ to the existing in-library context that $x_{g}$ was matched to. Denote $f_{g}$ as the existing context whose custom action $x_{g}$ was assigned to. According to the “triangular inequality” shown as Equation (13) (up to constant coefficient), we have: $E[l_{t}]\leq O(d(x_{t},f_{g}))\leq O(d(x_{t},c_{i}^{\star})+d(c_{i}^{\star},f_{g}))\leq O(d(x_{t},c_{i}^{\star})+d(c_{i}^{\star},x_{g})+d(x_{g},f_{g}))=O(d(x_{t},c_{i}^{\star})+d(x_{g},c_{i}^{\star})+E[l_{g}])$.
If there is no such a $x_{g}$ (with very small probability), then we upper bound the expected loss by $c$. For a detailed proof of [Lemma˜B.6](https://arxiv.org/html/2509.25777v1#A2.Thmtheorem6), please kindly refer to [Section˜B.4](https://arxiv.org/html/2509.25777v1#A2.SS4).
∎

Combining [Lemma˜B.4](https://arxiv.org/html/2509.25777v1#A2.Thmtheorem4) and [Lemma˜B.6](https://arxiv.org/html/2509.25777v1#A2.Thmtheorem6) above, we have

$$ $\displaystyle\mathbb{E}[\sum_{t:x_{t}\in C_{i}^{*}}l_{t}]$ (21) $\displaystyle=$ $\displaystyle\mathbb{E}[\mathbb{E}[\sum_{t:x_{t}\in C_{i}^{*}}l_{t}|Z]]$ $\displaystyle=$ $\displaystyle\mathbb{E}[\mathbb{E}[\sum_{s:x_{s}\in C_{i}^{g}}l_{s}|Z]+\mathbb{E}[\sum_{r:x_{r}\in C_{i}^{b}}l_{r}|Z]]$ $\displaystyle=$ $\displaystyle\mathbb{E}[\mathbb{E}[\sum_{t:x_{t}\in C_{i}^{*}}l_{t}|\{x_{t}\}_{t=1}^{T}]+\mathbb{E}[\sum_{r:x_{r}\in C_{i}^{b}}l_{r}|Z]]$ $\displaystyle\leq$ $\displaystyle\mathbb{E}[3c+4A_{i}^{*}+4\sum_{s:x_{s}\in C_{i}^{g}}d(x_{s},c_{i}^{*})+6\sum_{s:x_{s}\in C_{i}^{g}}\Delta_{s}(x_{s},f_{s})]$ $\displaystyle+\mathbb{E}[4\sum_{r:x_{r}\in C_{i}^{b}}d(x_{r},c_{i}^{*})+4\sum_{r:x_{r}\in C_{i}^{b}}\Delta_{r}(x_{r},f_{r})$ $\displaystyle+\frac{|C_{i}^{*}|}{2}\cdot\frac{2}{|C_{i}^{*}|}\cdot(c+8\sum_{s:x_{s}\in C_{i}^{g}}\mathbb{E}[l_{s}]+8\sum_{s:x_{s}\in C_{i}^{g}}d(x_{s},c_{i}^{*}))]$ $\displaystyle\leq$ $\displaystyle\mathbb{E}[8c+0A_{i}^{*}+0\sum_{s:x_{s}\in C_{i}^{g}}d(x_{s},c_{i}^{*})+4\sum_{t:x_{t}\in C_{i}^{*}}\Delta_{t}(x_{t},f_{t})]$ $\displaystyle\leq$ $\displaystyle\mathbb{E}[8c+0A_{i}^{*}+4\sum_{t:x_{t}\in C_{i}^{*}}\Delta_{t}(x_{t},f_{t})].$ $$

Here the last inequality is because $\sum_{s:x_{s}\in C_{i}^{g}}d(x_{s},c_{i}^{*})\leq\frac{\sum_{s:x_{s}\in C_{i}^{g}}+\sum_{r:x_{r}\in C_{i}^{b}}}{2}=\frac{A_{i}^{2}}{2}$. On the other hand, the sum of losses in $OPT_{o}$ that are associated to $c_{i}^{*}$ equals $c+A_{i}^{*}$. Therefore, we have $ALG\leq 60OPT_{o}+54\sum_{t=1}^{T}\Delta_{t}(x_{t},f_{t})$. This ends the proof of [Lemma˜B.3](https://arxiv.org/html/2509.25777v1#A2.Thmtheorem3).
∎

###### Remark B.7 .

The reason for us to divide $\{x_{t}\}$’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](https://arxiv.org/html/2509.25777v1#A2.Thmtheorem5) such that the Case I(c) and Case II hold. [Lemma˜B.5](https://arxiv.org/html/2509.25777v1#A2.Thmtheorem5) states that for any group of $\{x_{t}\}$’s, the expected cost before a new action being created (i.e. before a new context is added to the library) among them is no more than $c$. Therefore, if there does not exist an $e_{i}$ close enough to $c_{i}^{*}$, we know that no new actions have been created among good $\{x_{t}\}$’s (since any good $x_{t}$ satisfies $d(x_{t},c_{i}^{*})\leq 2a_{i}^{*}$ and therefore is a qualified candidate $e_{i}$ 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_{i}^{*}$.
- (2)
We can only upper-bound the *individual* loss of each bad $x_{t}$ due to the reason in (1) above. The individual upper bound for a bad point is applicable for a good point, but this would introduce a linear dependence on $T\cdot c$ in the overall loss instead of a 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 error of online linear regression with least-square estimator satisfies $\sum_{t=1}^{T}\Delta_{t}=O(\sqrt{d^{2}T\log T})$.

We defer the proof of [Lemma˜B.8](https://arxiv.org/html/2509.25777v1#A2.Thmtheorem8) to [Section˜B.5](https://arxiv.org/html/2509.25777v1#A2.SS5) as a standard result from linear regression. According to what we stated earlier, this completes the proof of [Theorem˜5.4](https://arxiv.org/html/2509.25777v1#S5.Thmtheorem4).

In the following subsections, we present the proof details of lemmas proposed above.

###### Lemma B.1 ( O ​ P ​ T o OPT_{o} upper bound) .

###### Proof sketch.

###### Lemma B.2 ( Δ t \Delta_{t} as estimation error) .

###### Lemma B.3 (Constant competitive ratio) .

###### Proof.

###### Lemma B.4 .

###### Proof of Lemma ˜ B.4 .

###### Lemma B.5 (Constant loss bound before a new action being generated) .

###### Lemma B.6 .

###### Proof sketch of Lemma ˜ B.6

###### Remark B.7 .

###### Lemma B.8 (Linear regression excess risk) .

### B.1 Proof of Lemma ˜ B.1

###### Proof.

Let $\tilde{S}=\{[N_{1},N_{2},\ldots,N_{d}]^{\top}|N_{i}\in[\frac{1}{\Delta}],i=1,2,\ldots,d\}$. On the one hand, for any context $x=[x_{1},x_{2},\ldots,x_{d}]^{\top}\in\mathbb{R}^{d},\|x\|_{2}\leq 1$, consider $f_{x}:=[\lfloor\frac{x_{1}}{\Delta}\rfloor\cdot\Delta,\lfloor\frac{x_{2}}{\Delta}\rfloor\cdot\Delta,\ldots,\lfloor\frac{x_{d}}{\Delta}\rfloor\cdot\Delta]$. Due to the definition of $\tilde{S}$, we know that $f_{x}\in\tilde{S}$. Also we have $d(x,f_{x})=\|x-f_{x}\|_{W}^{2}<\|[\Delta,\Delta,\ldots,\Delta]^{\top}\|_{W}^{2}\leq\lambda_{\max}(W)\cdot\Delta^{2}d$. On the other hand, we have $|\tilde{S}|=(\frac{1}{\Delta})^{d}$. Denote $S^{*}$ as the solution to $OPT_{o}$ (as defined in [Equation˜9](https://arxiv.org/html/2509.25777v1#A2.E9)), we have

$$ $\displaystyle OPT_{o}=$ $\displaystyle c\cdot|S^{*}|+\sum_{t=1}^{T}\min_{f\in S^{*}}d(x_{t},f)$ (22) $\displaystyle\leq$ $\displaystyle c\cdot|\tilde{S}|+\sum_{t=1}^{T}\min_{f\in\tilde{S}}d(x_{t},f)$ $\displaystyle\leq$ $\displaystyle c\cdot(\frac{1}{\Delta})^{d}+\sum_{t=1}^{T}d(x_{t},f_{x_{t}})$ $\displaystyle\leq$ $\displaystyle c(\frac{1}{\Delta})^{d}+T\cdot\lambda_{\max}(W)\cdot\Delta^{2}d$ $\displaystyle=$ $\displaystyle O(\frac{1}{\Delta^{d}}+T\Delta^{2}d),$ $$

and we let $\Delta=T^{-\frac{1}{d+2}}d^{-\frac{1}{d+2}}$ to make the RHS = $O(T^{\frac{d}{d+2}}d^{\frac{d}{d+2}})$. This proves the lemma.
∎

###### Proof.

### B.2 Proof of Lemma ˜ B.2

###### Proof.

Here we prove a more general result on ridge regression:

###### Lemma B.9 .

Let $x_{1},x_{2},\ldots,x_{n}\in\mathbb{R}^{d}$ are $d$-dimension vectors, and $y_{i}:=x_{i}^{\top}\theta^{*}+N_{t}$, where $\theta^{*}\in\mathbb{R}^{d}$ is a fixed unknown vector such that $\|\theta^{*}\|_{2}\leq 1$ ,and $N_{t}$ is a *martingale difference sequence* subject to $\sigma$-subGaussian distributions. Denote $X=[x_{1},x_{2},\ldots,x_{n}]^{\top}\in\mathbb{R}^{n\times d}$ and $Y=[y_{1},y_{2},\ldots,y_{n}]^{\top}\in\mathbb{R}^{n}$. Let the ridge regression estimator

$$ $\hat{\theta}:=(X^{\top}X+I_{d})^{-1}X^{\top}Y$ $$

where $I_{d}$ is the $d\times d$ identity matrix. Then with probability $\Pr\geq 1-\delta$, we have

$$ $\displaystyle|x^{\top}(\theta^{*}-\hat{\theta})|\leq O\left((1+\sqrt{\log(\frac{2}{\delta})})\sqrt{x^{\top}(X^{\top}X+I_{d})^{-1}x}\right)$ (23) $$

holds for any $\delta>0$ and $x\in\mathbb{R}^{d}$.

###### Proof of Lemma ˜ B.9 .

Denote $N:=[N_{1},N_{2},\ldots,N_{n}]^{\top}\in\mathbb{R}^{n}$ as the vector of noises in the labels. Then we have

$$ $\displaystyle\hat{\theta}=(X^{\top}X+I_{d})^{-1}X^{\top}X\theta^{*}+(X^{\top}X+I_{d})^{-1}X^{\top}N.$ (24) $$

Therefore, the difference between $\theta^{*}$ and $\hat{\theta}$ can be characterized as

$$ $\displaystyle\theta^{*}-\hat{\theta}$ $\displaystyle=\theta^{*}-(X^{\top}X+I_{d})^{-1}X^{\top}X\theta^{*}-(X^{\top}X+I_{d})^{-1}X^{\top}N$ (25) $\displaystyle=(X^{\top}X+I_{d})^{-1}(X^{\top}X+I_{d})\theta^{*}-(X^{\top}X+I_{d})^{-1}X^{\top}X\theta^{*}-(X^{\top}X+I_{d})^{-1}X^{\top}N$ $\displaystyle=(X^{\top}X+I_{d})^{-1}\theta^{*}-(X^{\top}X+I_{d})^{-1}X^{\top}N$ $\displaystyle=(X^{\top}X+I_{d})^{-1}(\theta^{*}-X^{\top}N).$ $$

As a result, we have

$$ $\displaystyle|x^{\top}(\theta^{*}-\hat{\theta})|$ $\displaystyle=|x^{\top}(X^{\top}X+I_{d})^{-1}(\theta^{*}-X^{\top}N)|$ (26) $\displaystyle\leq|x^{\top}(X^{\top}X+I_{d})^{-1}\theta^{*}|+|x^{\top}(X^{\top}X+I_{d})^{-1}X^{\top}N|.$ $$

For the simplicity of notation, denote $A:=(X^{\top}X+I_{d})^{-}1$, then we have $|x^{\top}(\theta^{*}-\hat{\theta})|\leq\|x^{\top}A\theta^{*}\|_{2}+\|x^{\top}AX^{\top}N\|$. On the one hand, for the first term we have

$$ $\displaystyle|x^{\top}A\theta^{*}|$ $\displaystyle\leq\|A^{\top}x\|_{2}\cdot\|\theta^{*}\|_{2}$ (27) $\displaystyle\leq\sqrt{x^{\top}AA^{\top}x}\cdot 1$ $\displaystyle\leq\sqrt{x^{\top}Ax}.$ $$

The second line is because $\|\theta^{*}\|\leq 1$, and the last inequality is because $A=A^{\top}=(X^{\top}X+I_{d})^{-1}\prec I_{d}$.

On the other hand, for the second term, recall that we set $A:=(X^{\top}X+I_{d})^{-1}\quad\text{and}\quad\theta^{*}-\hat{\theta}=A\left(\theta^{*}-X^{\top}N\right).$ We consider the random variable $x^{\top}AX^{\top}N=\sum_{t=1}^{n}\alpha_{t}N_{t},$ where the deterministic coefficients $\alpha_{t}:=\left(x^{\top}AX^{\top}\right)_{t},\quad t=1,\ldots,n.$

Notice that $\{N_{t}\}$ is a martingale difference sequence with subGaussian tails. According to Jin et al. [2019, Proposition 7], which is a subGaussian version of Azuma–Hoeffding’s Inequality, let $d=1$ and there exists a constant $C_{J}$ such that

$$ $\displaystyle\Bigl|\sum_{t=1}^{n}\alpha_{t}N_{t}\Bigr|\leq C_{J}\cdot\sqrt{\sum_{t=1}^{n}\alpha_{t}^{2}\log\frac{2}{\delta}}.$ (28) $$

with probability $\Pr\geq 1-\delta$. Here $\|\alpha\|_{2}^{2}=\sum_{t=1}^{n}\alpha_{t}^{2}=x^{\top}A\,X^{\top}X\,A\,x\leq x^{\top}A\,x$ because $X^{\top}X\preceq X^{\top}X+I_{d}$.

Therefore, with probability at least $1-\delta$,

$$ $\bigl|x^{\top}AX^{\top}N\bigr|\leq C_{J}\sqrt{\,x^{\top}A\,x\,\log\left(\frac{2}{\delta}\right)}.$ (29) $$

Returning to $|x^{\top}(\theta^{*}-\hat{\theta})|\leq|x^{\top}A\,\theta^{*}|+|x^{\top}A\,X^{\top}N|,$ we already established (using $\|\theta^{*}\|_{2}\leq 1$) that $|x^{\top}A\,\theta^{*}|\leq\sqrt{x^{\top}A\,x}.$
Combining this with [Equation˜29](https://arxiv.org/html/2509.25777v1#A2.E29) as the martingale tail bound, we get

$$ $\displaystyle|x^{\top}(\theta^{*}-\hat{\theta})|\leq$ $\displaystyle\sqrt{x^{\top}A\,x}+C_{J}\cdot\sqrt{\,x^{\top}A\,x\,\log\left(\frac{2}{\delta}\right)}$ (30) $\displaystyle=$ $\displaystyle\left(1+C_{J}\cdot\sqrt{\,\log\left(\frac{2}{\delta}\right)}\right)\,\sqrt{x^{\top}(X^{\top}X+I_{d})^{-1}\,x}.$ $$

This ends the proof of [Lemma˜B.9](https://arxiv.org/html/2509.25777v1#A2.Thmtheorem9).

∎

Now let us go back to the proof of [Lemma˜B.2](https://arxiv.org/html/2509.25777v1#A2.Thmtheorem2). We apply this lemma for $6T$ times: in the proof of [Lemma˜B.4](https://arxiv.org/html/2509.25777v1#A2.Thmtheorem4) as Case I(a), I(b), I(c) (or Lemma 5.6) and II, and in the proof of [Lemma˜B.6](https://arxiv.org/html/2509.25777v1#A2.Thmtheorem6) as Case I and Case II, in each of which we adopt this concentration bound for each existing context $f\in S_{t}$, which is at most $T$. Therefore, we let $\delta\leftarrow\frac{1}{6T^{2}}\delta$ and let $\lambda=1$, $\alpha=(1+C_{J}\cdot\sqrt{\log\frac{12T^{2}}{\delta}})\cdot\|W\|_{F}$. According to [Lemma˜B.9](https://arxiv.org/html/2509.25777v1#A2.Thmtheorem9), we prove that $\bar{d}(x_{t},f)-\Delta_{t}(x_{t},f)\leq d(x_{t},f)\leq\bar{d}(x_{t},f)+\Delta_{t}(x_{t},f)$ holds for any $f\in S_{t}$ and $\forall t=1,2,\ldots,T$, with probability $\Pr\geq 1-\delta$. Therefore, we have proved [Lemma˜B.2](https://arxiv.org/html/2509.25777v1#A2.Thmtheorem2).
∎

###### Proof.

###### Lemma B.9 .

###### Proof of Lemma ˜ B.9 .

### B.3 Proof of Lemma ˜ B.5

###### Proof.

Notice that at each time $t_{k}$, with probability $\Pr=\frac{\hat{d}_{t_{k}}(x_{t_{k}},f_{t_{k}})}{c}$ we terminate this stochastic process, and with the rest $\Pr=1-\frac{\hat{d}_{t_{k}}(x_{t_{k}},f_{t_{k}})}{c}$ we add $d_{t_{k}}(x_{t_{k}},f_{t_{k}})$ to our cumulative expected loss. Since $\hat{d}_{t_{k}}(x_{t_{k}},f_{t_{k}})\geq d_{t_{k}}(x_{t_{k}},f_{t_{k}}),\forall k\in[n]$, we may instead prove a generalized version of this lemma.

###### Lemma B.10 .

Consider an infinite sequence $\{p_{1},p_{2},\ldots,p_{k},\ldots\}$ where $p_{k}\in[0,1]$. The initial sum $S=0$. At each time $k$, with probability $p_{k}$ we *stop* this stochastic process, otherwise we add $p_{k}$ to the sum $S$. We show that $\mathbb{E}[S]\leq 1$.

[Lemma˜B.10](https://arxiv.org/html/2509.25777v1#A2.Thmtheorem10) is a generalization of [Lemma˜B.5](https://arxiv.org/html/2509.25777v1#A2.Thmtheorem5) since we add $d_{t_{k}}(x_{t_{k}},f_{t_{k}})\leq\hat{d}_{t_{k}}(x_{t_{k}},f_{t_{k}})$ at each time $k$ in the latter setting.

Denote a random variable $I_{k}$ as follows: $I_{k}=1$ if the stochastic process has not stopped by the end of time $k$, and $I_{k}=0$ otherwise. In the case when $I_{k}=1$, we add $p_{k}$ to the sum $S$. Therefore, we have

$$ $\mathbb{E}[S]=\sum_{k=1}^{\infty}p_{k}I_{k}$ $$

. Also, we know that the probability that $I_{k}=1$ is $\Pr[I_{k}=1]=\prod_{i=1}^{k}(1-p_{i}).$ As a result, we have

$$ $\displaystyle\mathbb{E}[S]$ $\displaystyle=\mathbb{E}[\sum_{k=1}^{\infty}p_{k}\cdot I_{k}]$ (31) $\displaystyle=\sum_{k=1}^{\infty}p_{k}\prod_{i=1}^{k}(1-p_{i}).$ $$

In the following, we show that $\sum_{k=1}^{\infty}p_{k}\prod_{i=1}^{k}(1-p_{i})\leq 1$. We first consider $p_{k}\in(0,1)$. Denote $Q_{0}:=1$ and $Q_{k}:=\Pr[I_{k}=1]=\prod_{i=1}^{k}(1-p_{i})$, and we know $Q_{k}=(1-p_{k})Q_{k-1}\leq Q_{k-1}$. Also, we have $p_{k}Q_{k-1}=(1-(1-p_{k}))Q_{k-1}=Q_{k-1}-Q_{k}$.

For the rigorousness of the proof, we first show that $\sum_{k=1}^{\infty}p_{k}Q_{k}$ is finite. Denote

$$ $T_{n}:=\sum_{k=1}^{n}p_{k}Q_{k},$ (32) $$

and we have

$$ $\displaystyle T_{n}\leq$ $\displaystyle\sum_{k=1}^{n}p_{k}Q_{k-1}$ (33) $\displaystyle=$ $\displaystyle\sum_{k=1}^{n}Q_{k-1}-Q_{k}$ $\displaystyle=$ $\displaystyle Q_{0}-Q_{n}$ $\displaystyle<$ $\displaystyle Q_{0}=1$ $$

As $T_{n}<1$ and $T_{n+1}\geq T_{n},\forall n\geq 1$, we have

$$ $\lim_{n\rightarrow\infty}T_{n}\leq 1$ (34) $$

according to the Monotone Convergence Theorem.
Then we slightly generalize the results above from $p_{k}\in(0,1)$ to $p_{k}\in[0,1]$, i.e. incorporating 0 and $1$. In fact, if $p_{k}=0$, then we may skip this $p_{k}Q_{k}$ term. Otherwise if $p_{k}=1$, consider the first $m$ s.t. $p_{m}=1$, and then we still have $E[S]=\sum_{k=1}^{m-1}p_{k}I_{k}=T_{m-1}<1$ and $I_{m}=I_{M}=0$ for any $M\geq m,M\in\mathbb{Z}^{+}$.

Therefore, we have

$$ $\displaystyle\mathbb{E}[S]=$ $\displaystyle\sum_{k=1}^{\infty}p_{k}Q_{k}$ (35) $\displaystyle\leq$ $\displaystyle\sum_{k=1}^{\infty}p_{k}Q_{k-1}$ $\displaystyle=$ $\displaystyle\sum_{k=1}^{\infty}Q_{k-1}-Q_{k}$ $\displaystyle=$ $\displaystyle Q_{0}-\lim_{k\rightarrow\infty}Q_{k}$ $\displaystyle\leq$ $\displaystyle 1.$ $$

This ends the proof of [Lemma˜B.10](https://arxiv.org/html/2509.25777v1#A2.Thmtheorem10) and therefore proves [Lemma˜B.5](https://arxiv.org/html/2509.25777v1#A2.Thmtheorem5).
∎

###### Proof.

###### Lemma B.10 .

### B.4 Proof of Lemma ˜ B.6

###### Proof.

Consider the moment when a $x_{t}\in C_{i}^{b}$ arrives, and denote $s$ as the most recent moment ($s<t$) such that $x_{s}\in C_{i}^{g}$. According to the uniform permutation assumption from $Z$ to $\{x_{t}\}_{t=1}^{T}$, this $x_{s}$ can be any $z\in C_{i}^{g}$ with equal probability as $\Pr=\frac{1}{|C_{i}^{g}|}=\frac{2}{|C_{i}^{*}|}$. In the following, we analyze the expected loss $\mathbb{E}[l_{t}]$ by two cases:

- (I)
If $x_{s}\in C_{i}^{g}$ does exist before $x_{t}$ occurs. Denote $f_{t}^{*}:=\operatorname*{arg,min}_{f\in S_{t}}d(c_{i}^{*},f)$ as the closest context to $c_{i}^{*}$ existed by the time $t$. Then we have:
$\displaystyle\mathbb{E}[l_{t}|\{x_{t}\}_{t=1}^{T}]=$
$\displaystyle c\cdot\frac{\hat{d}_{t}(x_{t},f_{t})}{c}+d(x_{t},f_{t})\cdot(1-\frac{\hat{d}_{t}(x_{t},f_{t})}{c})$
(36)
$\displaystyle\leq$
$\displaystyle\hat{d}_{t}(x_{t},f_{t})+d(x_{t},f_{t})$
$\displaystyle\leq$
$\displaystyle\check{d}_{t}(x_{t},f_{t})+2\Delta_{t}+\check{d}_{t}(x_{t},f_{t})+2\Delta_{t}$
$\displaystyle\leq$
$\displaystyle 2\check{d}_{t}(x_{t},f_{t}^{*})+4\Delta_{t}$
$\displaystyle\leq$
$\displaystyle 2d(x_{t},f_{t}^{*})+4\Delta_{t}$
$\displaystyle\leq$
$\displaystyle 4d(x_{t},c_{i}^{*})+4d(c_{i}^{*},f_{s}^{*})+4\Delta_{t}.$
Also, denote $\hat{f}_{s}:=\operatorname*{arg,min}_{f\in S_{s}}d(x_{s},f)$ as the best existing context that can be matched to $x_{s}$ by the time $s$. Then we know that
$\displaystyle\mathbb{E}[l_{s}|\{x_{t}\}_{t=1}^{T}]$
$\displaystyle\geq d(x_{s},\hat{f}_{s})$
(37)
$\displaystyle\geq\frac{1}{2}d(c_{i}^{*},\hat{f}_{s})-d(x_{s},c_{i}^{*})$
$\displaystyle\geq\frac{1}{2}d(c_{i}^{*},f_{s}^{*})-d(x_{s},c_{i}^{*}).$
Combining [Equation˜36](https://arxiv.org/html/2509.25777v1#A2.E36) with [Equation˜37](https://arxiv.org/html/2509.25777v1#A2.E37), we have
$\displaystyle\mathbb{E}[l_{t}|\{x_{t}\}_{t=1}^{T}]$
$\displaystyle\leq 4d(x_{t},c_{i}^{*})+4\Delta_{t}+4\cdot 2(\mathbb{E}[l_{s}|\{x_{t}\}_{t=1}^{T}]+d(x_{s},c_{i}^{*}))$
(38)
$\displaystyle\leq 4d_{t}^{*}+2\Delta_{t}+8\cdot\frac{2}{|C_{i}^{*}|}\cdot(\sum_{s:x_{s}\in C_{i}^{g}}\mathbb{E}[l_{s}|\{x_{t}\}_{t=1}^{T}]+d_{s}^{*}).$
Again, the last line of [Equation˜38](https://arxiv.org/html/2509.25777v1#A2.E38) comes from the i.i.d. assumption of $x_{s}$.
- (II)
If $x_{s}\in C_{i}^{g}$ does not exist before $x_{t}$ occurs, i.e. $x_{r}\in C_{i}^{b},\forall r\leq t-1$. According to the uniform permutation from $Z$ to $\{x_{t}\}_{t=1}^{T}$, this event happens with probability $\frac{2}{|C_{i}^{*}|}$. In this case, if $\hat{d}_{t}(x_{t},f_{t})\geq c$, then we suffer a cost $c$ at time $t$; otherwise $\hat{d}_{t}(x_{t},f_{t})<c$, and we either generate a new action (with cost $c$) or suffer an expected loss at $d(x_{t},f_{t})\leq\hat{d}_{t}(x_{t},f_{t})<c$. In a nutshell, the expected loss does not exceed $c$.

Combining with Case I and Case II above, we immediately get [Equation˜20](https://arxiv.org/html/2509.25777v1#A2.E20).
∎

###### Proof.

### B.5 Proof of Lemma ˜ B.8

###### Proof.

Denote $\Delta_{t}:=\Delta_{t}(x_{t},f_{t})$ for simplicity. In the following, we first reduce the summation of estimation error $\Delta_{t}$ to the regret of a $K(\leq T)$-arm linear bandit problem, up to constant factors. In fact, according to [Lemma˜B.2](https://arxiv.org/html/2509.25777v1#A2.Thmtheorem2), we know that $d(x_{t},f)\leq\check{d}_{t}(x_{t},f)\leq d(x_{t},f)$. Since we select $f_{t}=\operatorname*{arg,min}_{f\in S_{t}}\check{d}_{t}(x_{t},f)$, we have

$$ $\displaystyle d(x_{t},f_{t}^{*})-2\Delta_{t}\leq$ $\displaystyle d(x_{t},f_{t})-2\Delta_{t}$ (39) $\displaystyle\leq$ $\displaystyle\check{d}_{t}(x_{t},f_{t})$ $\displaystyle\leq$ $\displaystyle\check{d}_{t}(x_{t},f_{t}^{*})$ $\displaystyle\leq$ $\displaystyle d(x_{t},f_{t}^{*}),$ $$

where $f_{t}^{*}:=\operatorname*{arg,min}_{f\in S_{t}}d(x_{t},f)$ as the best existing context for $x$ in the current context library at time $t$. Therefore, the performance gap between $f_{t}$ and $f_{t}^{*}$ can be bounded as $d(x_{t},f_{t})-d(x_{t},f_{t}^{*})\leq 2\Delta_{t}$. On the other hand, since $d(x_{t},f_{t})=<w,\phi(x_{t},f_{t})>$ is a linear loss function, we consider $\phi(x_{t},f)$ as the “context”(^4^44Here we denote this covariate as the *context* as it serves as an environmental description in the contextual bandits. We denote $f\in S_{t}$, which was denoted as a context in the library, an *arm* of this contextual bandits.)
of each arm $f\in S_{t}$, and then we form a linear contextual bandit problem setting. Recall that $\Delta_{t}=\alpha\cdot\sqrt{\phi(x_{t},f_{t})^{\top}\Sigma_{t-1}^{-1}\phi(x_{t},f_{t})}$. According to Chu et al. [2011] Lemma 3 (which originates from Auer [2002] Lemma 13), we have

$$ $\displaystyle\sum_{t=1}^{T}\Delta_{t}$ $\displaystyle=\sum_{t=1}^{T}\alpha\cdot\sqrt{\phi(x_{t},f_{t})^{\top}\Sigma_{t-1}^{-1}\phi(x_{t},f_{t})}$ (40) $\displaystyle\leq\alpha\cdot 5\sqrt{(d^{2})|\Psi_{T+1}|\log|\Psi_{T+1}|}$ $\displaystyle\leq 5\alpha\sqrt{d^{2}T\log T}.$ $$

Here the second line is because the dimension of contexts are $d^{2}$ as $\phi(x_{t},f)=Vec((x_{t}-f)(x_{t}-f)^{\top})\in\mathbb{R}^{d^{2}}$, and the third line comes from the original definition of $\Psi_{t}$ as a subset of $[t-1]$.
∎

###### Proof.

### B.6 Proof of Lower Bound ( Theorem ˜ 5.5 )

###### Proof.

In order to prove the lower bound, we show the following facts

- 1.
$OPT_{o}=\Omega(T^{\frac{d}{d+2}})$ according to the $K$-nearest-neighbors(K-NN) lower bound.
- 2.
Any online facility location algorithm suffers at least $(2-o(1))$-competitive-ratio, i.e. $ALG\geq(2-o(1))OPT_{h}$.

In the following, we present two lemmas corresponding to the facts above.

###### Lemma B.11 ( $OPT_{o}$ lower bound) .

We have $OPT_{h}\geq OPT_{o}\geq\Omega(T^{\frac{d}{d+2}})$.

###### Proof.

Denote

$$ $\displaystyle OPT_{o}(K)$ $\displaystyle=\min_{S:|S|=K}c\cdot|S|+\sum_{t=1}^{T}\min_{f\in S}d(x_{t},f)$ (41) $\displaystyle=K+T\cdot\min_{S:|S|=K}\frac{1}{T}\sum_{t=1}^{T}\min_{f\in S}d(x_{t},f).$ $$

This equals $T$ times $K$-nearest-neighbors (K-NN) loss plus $K$. According to Zador [1964] (i.e. Zador’s Theorem in coding theory), the mean squared distance to the nearest codebook center in $\mathbb{R}^{d}$ space in $L_{r}$-norm is lower bounded by $\Omega(K^{-\frac{r}{d}})$. This is directly applicable to K-NN which effectively partitions points by their nearest neighbors. Hence, the quantization lower bound established by Zador’s Theorem translates into a lower bound on K-NN’s average squared loss. Therefore, we let $r=2$ to fit in our setting, and then have

$$ $\displaystyle OPT_{o}=$ $\displaystyle\min_{K\in[T]}OPT_{o}(K)=\Omega(c\cdot K+T\cdot K^{-\frac{2}{d}})=\Omega(T^{\frac{d}{d+2}}),$ (42) $$

where the last line is an application of Hölder’s Inequality that $K+T\cdot K^{-\frac{2}{d}}\geq K^{\frac{\frac{2}{d}}{1+\frac{2}{d}}}(T\cdot K^{-\frac{2}{d}})^{\frac{1}{1+\frac{2}{d}}}=T^{\frac{d}{d+2}}$, and the equality holds at $K=T^{\frac{d}{d+2}}$.
∎

###### Lemma B.12 (Theorem 5.1 in Kaplan et al. [ 2023 ] ) .

Let ${\mathcal{A}}$ be an algorithm for online facility location in the i.i.d. model, then, the competitive ratio of ${\mathcal{A}}$ is at least $2-o(1)$.

Combining [Lemma˜B.11](https://arxiv.org/html/2509.25777v1#A2.Thmtheorem11) and [Lemma˜B.12](https://arxiv.org/html/2509.25777v1#A2.Thmtheorem12), we know that $REG=ALG-OPT_{h}\geq(2-o(1)-1)OPT_{h}\geq 0.5OPT_{o}=\Omega(T^{\frac{d}{d+2}})$. This proves [Theorem˜5.5](https://arxiv.org/html/2509.25777v1#S5.Thmtheorem5)
∎

###### Proof.

###### Lemma B.11 ( O ​ P ​ T o OPT_{o} lower bound) .

###### Proof.

###### Lemma B.12 (Theorem 5.1 in Kaplan et al. [ 2023 ] ) .

## Peer Reviews

confidence: 4
contribution: 4
initial_rating: 8
presentation: 4
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})$?
2.  **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)?
3.  **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.
4.  **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$?
soundness: 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.
* **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.
* **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.
* **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.
* **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.
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.

To 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)$.

The paper's main contributions are:
1.  The "create-to-reuse" problem formulation.
2.  The novel Doubly-Optimistic Algorithm.
3.  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})$.
4.  A matching information-theoretic lower bound of $\Omega(T^{\frac{d}{d+2}})$ (with respect to $T$), proving the algorithm's optimality.
5.  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).
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.
* **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.
* **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.

---

confidence: 2
contribution: 3
initial_rating: 8
presentation: 3
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$).
- Would the regret-proof strategy still work under time- or context-dependent creation costs $c$? How do you envision your strategy to change?
soundness: 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.)_

The 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.
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.
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. 

I 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).

---

confidence: 2
contribution: 3
initial_rating: 6
presentation: 3
questions: Questions: 
- 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*
- 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.
soundness: 3
strengths: Strengths: 
- 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. 
- 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.
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). 

Notation: 
- Input context variable $x_t \in \mathbb{R}^d$ i.e. vector embedding for questions in FAQ setting
- $S_t:= \{x_t, a_t\}$ is a context library of vetted FAQs that is stored as a hash map. 
- $d(x,f)$ is the distance function which models the loss.
weaknesses: Weakness: 
- 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. 
- 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. 
- 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.
- 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*)

---

confidence: 3
contribution: 3
initial_rating: 6
presentation: 4
questions: 1) Is it possible to extend the analysis to the case where $W$ depends on the context $x_t$ ?
2) Are there other motivations for the problem studied in this paper?
soundness: 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. 
2) The setting is interesting and is well motivated from a practical point of view (healthcare QA)
3) 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).
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.
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$.
2) 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.

---

confidence: 4
contribution: 2
initial_rating: 6
presentation: 3
questions: 1. How critical is the quadratic assumption on mismatch loss? Would kernelized or neural distance functions maintain similar regret behavior?

2. Can the proposed framework handle context-dependent creation costs c(x_t)? How would this affect the theoretical analysis?

3. Could approximate nearest neighbor search or library pruning reduce complexity while preserving regret guarantees?

4. The create-to-reuse tradeoff resembles selective labeling. Could active learning techniques (e.g., expected information gain) enhance the creation policy?

5. How would the method extend to stochastic or partially observable generation outcomes (as in LLM-based action creation)?
soundness: 3
strengths: 1.  Introduces an important and timely extension of online decision-making- expanding the action space through generative capabilities.
2.  The double-optimism principle (LCB for reuse, UCB for creation) is conceptually appealing and well-motivated by the underlying tradeoffs.
3.  Provides nontrivial analysis, including tight regret bounds and a matching lower bound.
4. The healthcare Q&A examples effectively illustrate the value of balancing creation cost with reuse benefits.
5. Real-data results show meaningful gains and smooth generation-quality tradeoffs.
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.
To 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.
This 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),
which matches an  Ω(T^{d/(d+2)}) lower bound—making it optimal with respect to the time horizon T.
Empirical 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.
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).
   The paper proposes approximate implementations (linear or neural variants) but does not provide theoretical guarantees for them.

2.  The  quadratic loss model d(x,f) = (x-f)^\top W(x-f) may not generalize to real semantic spaces.
  
3.  Evaluation focuses mainly on healthcare QA; additional domains (e.g., recommendation systems or dynamic pricing) would strengthen claims of generality.

4.  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?

5.  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.


Decision: Accept (Poster)