Efficient Algorithms for Logistic Contextual Slate Bandits with Bandit Feedback

This paper introduces two efficient algorithms, Slate-GLM-OFU and Slate-GLM-TS, for the Logistic Contextual Slate Bandit problem that achieve $\tilde{O}(\sqrt{T})$ regret and $N^{O(1)}$ per-round computational complexity by combining local planning with global learning, demonstrating superior performance in both synthetic benchmarks and practical language model applications.

The Gist

Imagine you are running a digital billboard company. Every time a car drives by, you get a split second to decide what ad to show. But here's the twist: your billboard isn't just one image; it's a slate made of three different parts (slots).

• Slot 1: The headline.
• Slot 2: The image.
• Slot 3: The call-to-action button.

You have thousands of possible headlines, images, and buttons to choose from. The total number of combinations is astronomical (exponential). Your goal is to pick the perfect combination of Headline + Image + Button to get the most clicks (rewards).

The problem? You only get one piece of feedback: Did the driver click the ad or not? You don't know which part of the ad worked. Was it the funny headline? The bright red button? Or the picture of a dog? This is called Bandit Feedback.

This paper introduces a new way to solve this puzzle efficiently. Here is the breakdown in simple terms:

1. The Old Way: The "Brute Force" Nightmare

Imagine trying to find the best ad combination by testing every single possibility.

• If you have 100 headlines, 100 images, and 100 buttons, that's $100 \times 100 \times 100 = 1,000,000$ combinations.
• If you have 1,000 options for each, that's $1,000,000,000,000$ combinations.
• Checking them all one by one would take longer than the age of the universe. This is what older algorithms tried to do, and they failed because they were too slow.

2. The New Solution: "Local Planning" vs. "Global Learning"

The authors, Tanmay Goyal and Gaurav Sinha, propose two new algorithms (Slate-GLM-OFU and Slate-GLM-TS) that act like a smart, efficient manager. They use a clever trick: Separation of Concerns.

The Analogy: The Orchestra Conductor

Think of your ad slate as an orchestra.

• The Old Way: The conductor tries to rehearse every possible combination of instruments playing together to find the perfect song. It's chaotic and slow.
• The New Way: The conductor treats each instrument section (Strings, Brass, Percussion) separately.
  • Local Planning (The Soloists): The manager picks the best violin, the best trumpet, and the best drum independently. They don't need to check every possible trio. They just ask: "What's the best violin for this audience?" "What's the best trumpet?"
  • Global Learning (The Conductor): Even though they pick the instruments separately, the manager keeps a single notebook (a shared model) for the whole orchestra. When the audience claps (the reward), the manager updates the notebook for everyone. They learn that "When the violin plays fast, the audience likes it," and they apply that lesson to the trumpet and drums too.

3. How It Works in Practice

The paper uses a mathematical model called a Logistic Model (think of it as a probability calculator) to predict clicks.

• Step 1: The Setup. You have a slate with $N$ slots.
• Step 2: The Selection. Instead of looking at the massive list of all combinations, the algorithm looks at Slot 1, picks the best item based on current knowledge. Then it looks at Slot 2, picks the best item. Then Slot 3.
  • Why is this fast? Because picking the best item from a list of 1,000 is easy. Picking the best combination of 1,000 items from 3 lists is impossible. By doing them one by one, the computer work drops from "Exponential" (impossible) to "Linear" (fast).
• Step 3: The Feedback. You show the ad. You get a "Yes/No" (Click/No Click).
• Step 4: The Update. The algorithm updates its "Global Notebook." It realizes, "Okay, that specific combination worked." It uses that single data point to slightly adjust its understanding of all the slots simultaneously.

4. The "Diversity" Secret Sauce

For this "Local Planning" to work, the authors assume something called Diversity.

• The Metaphor: Imagine you are trying to learn what food people like. If you only serve them pizza every day, you'll never know if they like sushi.
• The Assumption: The algorithm assumes that over time, the items it picks will be diverse enough to cover all bases. If the algorithm picks a "sushi" item for Slot 1, it will eventually pick a "pizza" item too. This ensures the "Global Notebook" gets a complete picture of the world, allowing the separate slot decisions to eventually lead to the perfect global combination.

5. Real-World Results

The authors tested this in two ways:

1. Synthetic Tests: They created fake scenarios with thousands of combinations. Their algorithms were exponentially faster than the best existing methods and made fewer mistakes (lower "regret").
2. Real-World Test (AI Prompts): They used this to help AI (Language Models) write better answers.
   • The Task: The AI needs to pick the best "examples" to include in its prompt to solve a problem (like sentiment analysis).
   • The Result: By using their algorithm to pick the best examples, the AI achieved 80% accuracy, beating random guessing and competing with other advanced methods, but much faster.

Summary

This paper solves the problem of "Too many choices, too little feedback."

• Old Way: Try everything. (Too slow).
• New Way: Pick the best piece for each slot individually, but learn from the group result. (Fast and smart).

It's like building a perfect sandwich. Instead of tasting every possible combination of bread, meat, and cheese, you pick the best bread, the best meat, and the best cheese separately, but you keep a shared memory of which combinations made people happy, so you get better at it every time.

Technical Summary

Here is a detailed technical summary of the paper "Efficient Algorithms for Logistic Contextual Slate Bandits with Bandit Feedback."

1. Problem Definition

The paper addresses the Logistic Contextual Slate Bandit problem, a decision-making framework where an agent must select a "slate" (a set of $N$ items, one from each of $N$ distinct slots) at each round $t$.

• Contextual Setting: At each round, the available items for each slot are determined by contextual information (e.g., user query, history).
• Feedback: The agent receives only a single binary reward ($y_t \in \{0, 1\}$) for the entire selected slate, not individual rewards for each item. This is known as bandit feedback, which is more challenging than semi-bandit feedback (where item-level rewards are observed).
• Reward Model: The probability of receiving a reward of 1 is governed by a logistic model:
  $$P(y_t = 1 | x_t) = \mu(x_t^\top \theta^*) = \frac{1}{1 + \exp(-x_t^\top \theta^*)}$$
  where $x_t$ is the concatenated feature vector of the selected slate, and $\theta^*$ is an unknown parameter vector.
• Objective: Minimize cumulative regret over $T$ rounds.
• Challenge: The space of all possible slates is exponential ($2^{\Omega(N)}$). Standard bandit algorithms that treat every possible slate as a separate "arm" result in exponential time complexity per round, making them infeasible for large$N$. Furthermore, existing slate bandit algorithms often assume semi-bandit feedback or non-contextual (fixed-arm) settings, which do not apply here.

2. Methodology

The authors propose two new algorithms that achieve $N^{O(1)}$ (polynomial) per-round time complexity while maintaining optimal regret guarantees. The core innovation is a "local planning" strategy combined with "global learning."

Key Assumption: Diversity Assumption

The theoretical guarantees rely on a Diversity Assumption (Assumption 2.1). It posits that for each slot $i$, the expected feature matrix of selected items is full-rank and sufficiently large (bounded below by $\rho \kappa I$). This ensures that the algorithm explores the feature space sufficiently to learn the global parameter $\theta^*$.

Algorithm 1: Slate-GLM-OFU (Optimism in the Face of Uncertainty)

• Mechanism: Based on the OFU paradigm.
• Local Planning: Instead of optimizing over the entire slate space, the algorithm selects an item for each slot $i$ independently by maximizing an upper confidence bound:
  $$x_t^i = \arg\max_{x \in \mathcal{X}_t^i} \left( x^\top \theta_t^i + \sqrt{\eta_t(\delta)} \|x\|_{(W_t^i)^{-1}} \right)$$
  Here, $W_t^i$ is a slot-level design matrix updated using the global reward feedback.
• Global Learning: Despite selecting items independently, the algorithm maintains a single global parameter estimate $\theta_t$ and updates it using the observed slate-level reward $y_t$.
• Theoretical Insight: The authors prove that under the diversity assumption, the global design matrix $W_t$ (slate-level) and the block-diagonal matrix of slot-level matrices $\text{diag}(W_t^1, \dots, W_t^N)$ are multiplicatively equivalent. This allows the algorithm to use slot-level exploration bonuses to achieve global optimality.
• Regret: Achieves $\tilde{O}(dN\sqrt{T})$ regret (where $d$ is feature dimension, $N$ is slots).

Algorithm 2: Slate-GLM-TS (Thompson Sampling)

• Mechanism: Based on the Thompson Sampling paradigm.
• Local Perturbation: The algorithm samples noise vectors independently for each slot to perturb the parameter estimates:
  $$\tilde{\theta}_t^i = \theta_t^i + \eta_t(\delta)(W_t^i)^{-1/2}\eta^i$$
• Selection: It selects the optimal item for each slot based on the perturbed parameters $\tilde{\theta}_t^i$.
• Global Update: Like OFU, it updates the single global parameter $\theta_t$ using the slate-level reward via a sub-routine adapted from [FAJC22].
• Fixed-Arm Variant: The authors also propose Slate-GLM-TS-Fixed for non-contextual settings, proving $\tilde{O}(d^{3/2}N^{3/2}\sqrt{T})$ regret.

3. Key Contributions

1. Algorithm Design: Introduced Slate-GLM-OFU and Slate-GLM-TS, the first algorithms to solve the logistic contextual slate bandit problem under bandit feedback with polynomial time complexity.
2. Theoretical Guarantees: Proved that under the diversity assumption, Slate-GLM-OFU achieves a regret bound of $\tilde{O}(dN\sqrt{T})$, which is optimal and independent of the non-linearity parameter $\kappa$ (a common bottleneck in logistic bandits).
3. Efficiency: Demonstrated that by decoupling the selection process (local planning) while maintaining a unified model (global learning), the per-round complexity drops from exponential ($2^{\Omega(N)}$) to polynomial ($\text{poly}(N, \log T)$).
4. Empirical Validation: Extensive experiments showing the algorithms outperform state-of-the-art baselines in both regret and runtime.
5. Real-World Application: Applied the algorithm to Prompt Engineering for Large Language Models (LLMs), specifically selecting in-context examples for binary classification tasks.

4. Experimental Results

The authors conducted four sets of experiments:

• Experiment 1 (Contextual Regret): Compared against ada-OFU-ECOLog and TS-ECOLog (which treat slates as arms).
  • Result: Slate-GLM-OFU achieved the lowest regret in both finite and infinite context settings.
• Experiment 2 (Time Complexity): Varied the number of slots $N$ (3 to 6).
  • Result: Baselines showed exponential growth in runtime as $N$ increased. The proposed algorithms showed linear/polynomial growth, being orders of magnitude faster (e.g., seconds vs. minutes/hours for $N=6$).
• Experiment 3 (Non-Contextual/Fixed-Arm): Compared against MPS, Ordered-Slate-Bandit, and others.
  • Result: Slate-GLM-OFU achieved the best performance. MPS showed comparable average regret but high variance, making it less reliable.
• Experiment 4 (Prompt Tuning): Used Slate-GLM-OFU to select in-context examples for SST2 and Yelp Review sentiment analysis tasks using RoBERTa.
  • Result: Achieved competitive test accuracy (~80%), significantly outperforming random allocation baselines. The accuracy improved as the algorithm learned to select better examples over 5,000 rounds.

5. Significance

This work bridges a critical gap in the literature between theoretical optimality and computational feasibility in slate bandits.

• Scalability: It solves the "curse of dimensionality" inherent in slate selection by avoiding explicit enumeration of the slate space.
• Realism: It addresses the bandit feedback setting, which is prevalent in real-world applications like ad creative optimization and landing page design, where only aggregate conversion data is available.
• Practicality: The application to LLM prompt tuning demonstrates immediate utility in modern AI systems, offering a principled, data-efficient method for optimizing prompt components without requiring massive labeled datasets.

In summary, the paper provides a rigorous theoretical framework and highly efficient algorithms for optimizing complex, multi-component decisions under uncertainty and limited feedback, with proven applicability in both synthetic and real-world scenarios.