🤖 machine learning

Bootstrap-Conditioned Action Selection with Tabular Foundation Models

This paper proposes BC-ICL, a novel contextual bandit policy that leverages pre-trained tabular foundation models with in-context learning and bootstrap resampling to achieve sample-efficient, robust online decision-making that outperforms established baselines in sparse and cold-start scenarios.

Original authors: Devansh Gupta, Shiv Tavker, Dmitry Efimov, Suchitra Sathyanarayana, Gitanjali Bhutani, Boris N. Oreshkin

Published 2026-08-10

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Devansh Gupta, Shiv Tavker, Dmitry Efimov, Suchitra Sathyanarayana, Gitanjali Bhutani, Boris N. Oreshkin

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are the captain of a spaceship trying to find the best route through a vast, foggy galaxy. Every time you choose a path, you get a tiny hint—maybe a flash of light or a burst of static—telling you if you were close to the treasure or just flying into a dead end. This is the heart of a problem scientists call "contextual bandits." It's the math behind how computers learn to make personalized choices, like suggesting a movie you'll love or a song you'll dance to, based on who you are and what you've liked before. The tricky part is the "cold start": when the computer knows almost nothing about you, it has to guess wildly to learn. Traditional methods often get stuck guessing the same wrong thing over and over, or they get so nervous about being wrong that they stop trying new things. They need a way to be brave but smart, exploring the unknown without crashing the ship.

Enter a new crew member for your spaceship: a "foundation model." Think of this as a super-smart, pre-trained detective who has already read millions of mystery novels and knows how to spot patterns in data better than anyone. Usually, these detectives just sit there and give answers. But what if we could turn this detective into an explorer? That's exactly what the researchers in this paper, Devansh Gupta and his team, set out to do. They asked: Can we take this pre-trained detective, who is frozen and can't learn new tricks on the fly, and make it play a game of "guess the best move" by shaking up the clues it sees?

They built a method called BC-ICL (Bootstrap-conditioned action selection using ICL). Here is how it works in plain English: Imagine the detective is looking at a history of all the spaceship's past trips. Instead of looking at the whole history at once, the computer takes a "bootstrap" sample. This is like making a photocopy of the history log, but with a twist: it randomly picks some entries to include twice and leaves some out entirely, creating a slightly different, "what-if" version of the past. The frozen detective then looks at this new, slightly distorted version of history and makes a guess about the best path. Because the history log changed slightly, the detective's guess changes too. By repeating this process—shuffling the clues, asking the detective, and picking the best guess—the computer creates a strategy that naturally explores new paths without needing to retrain the detective from scratch.

To make this even better, the team added a special "arm-context" feature. Imagine the spaceship has many different engines (actions) it can use. Usually, a computer might treat each engine as a separate, isolated machine. But this new method treats the engines as a team. It uses a "multiplicative" map that lets the detective see how the current situation (the context) interacts with every engine at once. This means if the detective learns something about how the "speed" engine works in a storm, it can instantly apply that wisdom to the "steering" engine in the same storm. It's like a chef who, after learning how salt affects a tomato, immediately knows how salt will affect a mushroom, rather than having to taste-test every single vegetable separately.

The researchers tested this idea on a variety of challenging puzzles, from predicting whether a mushroom is poisonous to sorting handwritten digits. They found that BC-ICL was a star player. In many cases, it made fewer mistakes (a metric called "regret") than the old-school methods that rely on linear math or complex neural networks trained from scratch. For example, on a dataset called "Mushroom," the new method made 85% fewer mistakes than a popular neural network approach. Even more impressively, it did this while being surprisingly efficient; by using a smart way to pick which history logs to look at (like only remembering the most recent trips or the most similar ones), it could run almost as fast as the older methods, despite doing more complex thinking.

However, the paper also draws a clear line in the sand. They tested what happens if you just let the detective guess the "best" path every time without shuffling the history (a "greedy" approach). The results showed that this greedy strategy often fails, getting stuck on bad paths early on and never recovering. Similarly, just letting the detective's natural uncertainty guide the choices wasn't enough to beat the new method. The paper suggests that the magic isn't just in the detective's brain, but in the act of shaking up the clues before asking for an opinion. The researchers are confident in these results based on their simulations across eight different datasets, but they also note that this approach relies heavily on the detective having the right kind of pre-training. If the detective's past training doesn't match the current galaxy, the method might struggle. Still, for the right kind of data, this "shake-and-guess" strategy offers a powerful, practical way to turn a static, pre-trained model into a dynamic, exploratory decision-maker.

Technical Summary: Bootstrap-Conditioned Action Selection with Tabular Foundation Models

Problem Statement

Contextual bandits provide a framework for sample-efficient personalization, yet practical deployment is hindered by sparse and biased interaction data, unreliable uncertainty estimates, and severe cold-start scenarios. While global policy approaches are standard in large-scale systems to avoid the data inefficiency of per-user bandits, achieving principled exploration without sacrificing reward-model expressiveness remains difficult.

Classical methods often rely on linear reward models with optimism or posterior sampling, limiting representational power. Conversely, neural contextual bandit methods can model complex rewards but require training task-specific networks from scratch using only bandit feedback. Their uncertainty estimates (often based on linearization or dropout) are sensitive to hyperparameters and brittle in low-data regimes. Meanwhile, recent advances in In-Context Learning (ICL) for tabular data have produced powerful predictors (e.g., TabPFN, TabICL) that adapt to new tasks via a single forward pass, effectively amortizing Bayesian inference. However, it remains an open question whether these pretrained ICL predictors can be directly utilized for action selection in contextual bandits.

Methodology: BC-ICL

The authors propose BC-ICL (Bootstrap-conditioned action selection using ICL), a method that transforms a frozen, pretrained tabular ICL predictor into a randomized policy for online decision-making.

Core Mechanism

Instead of updating model parameters online, BC-ICL induces exploration by randomizing the conditioning history seen by the fixed backbone model. The algorithm operates as follows at each round $t$ :

Bootstrap Resampling: A bootstrap resample $\tilde{D}_t$ is drawn from the observed interaction history $D_t$ (sampling $|D_t|$ observations with replacement).
Conditioning: The frozen ICL predictor $M$ is conditioned on this resampled dataset $\tilde{D}_t$ .
Scoring: The model scores all candidate actions $a \in \mathcal{A}$ given the current context $x_t$ .
Selection: The action with the highest sampled score is selected: $a_t \in \arg\max_a \hat{\mu}_{\tilde{D}_t}(x_t, a)$ .
Update: The observed reward is appended to the history, and the process repeats.

Arm-Context Conditioning Architecture

To address the failure modes of isolated-arm bandits and promote shared statistical strength, the authors introduce a specific feature mapping $\Phi_{mult}(x, a)$ :
$\Phi_{mult}(x, a) = [x; e_a; (x^\top P) \odot e_a]$
Where:

$x$ is the raw context.
$e_a$ is a fixed arm embedding.
$P$ is a shared projection matrix.
$\odot$ denotes element-wise multiplication.

This representation preserves the raw context, encodes arm identity, and explicitly models arm-context interactions via the shared projected context. Crucially, perturbations in the conditioning history propagate through this common representation, affecting scores for multiple arms simultaneously, thereby enabling shared exploration.

Key Contributions

Algorithm Proposal: The introduction of BC-ICL, which couples bootstrap resampling with a frozen ICL predictor to convert a supervised model into an exploration-capable decision rule without online retraining.
Architectural Innovation: The design of a multiplicative arm-context feature map that facilitates shared exploration across actions through a common projected context representation.
Empirical Validation: Comprehensive evaluation demonstrating that BC-ICL (instantiated with TabPFN or TabICL) outperforms linear, kernelized, and neural contextual bandit baselines under strict online protocols.

Experimental Results

The authors evaluated BC-ICL on eight datasets (including UCI repositories like Covertype, ISOLET, Letter, and MNIST) converted into contextual bandit problems.

Performance: BC-ICL achieved the lowest cumulative regret across most datasets, substantially outperforming established baselines such as Linear TS, LinUCB, Kernel UCB/TS, NeuralUCB, NeuralTS, and BootstrapNN.
- Example: On the Mushroom dataset, BC-ICL-TabICL achieved a regret of 37.7 compared to 252.3 for NeuralTS (an 85% reduction).
- Example: On ISOLET, BC-ICL maintained consistently lower regret throughout the learning process compared to neural baselines.
Exploration Mechanism: Ablation studies revealed that the ICL model's internal predictive uncertainty alone (via greedy selection or sampling from the predictive distribution) is insufficient for effective sequential decision-making. The bootstrap resampling mechanism was shown to reduce regret by 5–19% over greedy and sampling baselines on challenging datasets, proving that data-level bootstrapping is necessary for effective exploration.
Feature Encoding: The multiplicative feature map ( $\Phi_{mult}$ ) significantly outperformed simple one-hot encoding ( $\Phi_{one-hot}$ ), reducing final regret by 30–40% on ISOLET, confirming the importance of explicitly modeling arm-context interactions.
Computational Efficiency: While using the full interaction history makes BC-ICL slower than neural baselines (e.g., 7x slower for TabPFN), the authors demonstrated that context selection strategies like KNN (nearest neighbors) or FIFO (sliding window) significantly reduce runtime while maintaining regret performance comparable to using the full history.

Significance and Claims

The paper claims that BC-ICL offers a practical and effective approach to contextual bandits by leveraging the inductive biases of pretrained tabular foundation models. By avoiding the need to train task-specific networks from scratch, the method achieves strong sample efficiency, particularly in cold-start and low-data regimes.

The authors note that the method assumes access to a pretrained model whose inductive biases align with the target task; performance may degrade if there is a significant prior-task mismatch. Furthermore, while the bootstrap procedure introduces computational overhead, the use of context selection strategies (KNN/FIFO) makes the approach scalable. Theoretically, the authors suggest that under mild stability assumptions, the regret of BC-ICL can be decomposed into a stability term and a representation term, though formalizing this remains a direction for future work.

The work supports the intuition that multiplicative arm-context representations enable useful statistical sharing across actions and that pretrained ICL models, when combined with bootstrap conditioning, can serve as robust, exploration-capable policies for online decision-making.