Papers for

online advertisers

Papers whose findings have a practical use for this group, as judged from the abstract. Open a paper to read what it means in practice.

Improved algorithms for selecting best item sets with limited feedback

Efficient Online Submodular Maximization with Bandit Feedback

Abstract: We study online monotone submodular maximization under a cardinality constraint with bandit feedback. On each round, the learner selects at most $k$ elements from a ground set of size $n$ and observes only the value of the selected set. We develop an efficient algorithm achieving $O\!\left(k\sqrt{nT\log(n/k)}\right)$ expected $(1-1/e)$-regret over $T$ rounds. To our knowledge, this is the first polynomial-time algorithm with $\sqrt{T}$ dependence on the horizon for arbitrary monotone submodular functions in the bandit setting. Our approach uses randomized sampling and a carefully constructed potential to reduce online submodular maximization to online linear optimization over the probability simplex.

Mon 9 NovMachine Learning
The gist
Sometimes we want to pick the best group of things from a big collection, but we only get very limited information about how good our choices are. This paper shows a new way for a computer to learn how to make better choices over time, even when it only sees the result of what it picked, not what it could have picked. The authors created an efficient method that keeps getting smarter as it tries more rounds, and it's the first that works well for a wide range of these problems. Their approach changes the hard problem into a simpler one that experts already know how to handle.
Open → 2611.11808v1

Slim models speed up online recommendation predictions with little accuracy loss

Slim Foundation Models for Latency-Critical Recommendation Serving

Abstract: Click-through rate (CTR) prediction is a core component of recommendation and advertising systems. Large language models (LLMs) offer rich semantic priors that improve prediction quality, particularly in cold-start and long-tail settings. Injecting a full-scale LLM into a CTR pipeline is, however, prohibitively expensive at inference time: existing LLM-enhanced CTR methods avoid this cost by caching LLM outputs offline rather than serving the LLM online. We propose a resource-efficient pipeline, SlimFM, that makes online LLM-based semantic modeling practical: (1) dependency-aware structured pruning compresses LLaMA3-8B by 44% to a 4.5B-parameter backbone; (2) LoRA-based field-aware fine-tuning trains the pruned model to produce discriminative field-level semantic embeddings from lightweight textual prompts; (3) a semantic-guided fusion module injects these embeddings into the feature interactions of a conventional CTR model. Across four datasets and six CTR backbones, SlimFM retains over 99% of uncompressed-model accuracy while reducing inference latency by up to 3.4x relative to existing LLM-enhanced baselines.

Sat 7 NovInformation RetrievalArtificial Intelligence
The gist
Online systems that suggest things to click on, like ads or products, rely on predicting how likely you are to click something. Big language models help these predictions but are too slow for real-time use. The authors created a smaller, faster version of such a model that keeps almost all the accuracy while making predictions up to 3.4 times faster. They do this by cutting the big model down, tuning it efficiently, and cleverly combining its output with regular recommendation software.
Open → 2611.11013v1

Algorithm ensures reliable decision making without knowing reward scale

Reliable Scale-Free Bandits via Empirical Likelihood

Abstract: We study stochastic bandits without knowledge of reward scales or tail parameters. Almost-sure regret guarantees describe eventual learning but do not quantify expected performance or the risk of large regret in a finite run. We introduce $\texttt{EL-F}$, an anytime empirical-likelihood (EL) extension of the $g$-Forcing policy of Cowan and Katehakis (2020), and characterize its performance at three levels. First, for integrable rewards and non-decreasing, diverging exploration schedules $g$ with vanishing increments, $\texttt{EL-F}$ preserves the $g$-Forcing asymptotics for pseudo-regret $R(T)$: $R(T)/g(T)\to\sum_{i:Δ_i>0}Δ_i$ almost surely as $T\to\infty$, where $Δ_i$ is the suboptimality gap of arm $i$. Second, on every sub-exponential instance, for non-decreasing $g(t)=ω(\log t)$ satisfying a mild feasibility condition, expected pseudo-regret is at most $g(T)\sum_{i:Δ_i>0}Δ_i+C_{\underline{P}}$, where $C_{\underline{P}}$ is an instance-dependent constant independent of $T$. Moreover, we also establish finite-time tail bounds with super-polynomial decay in regret beyond the forced-exploration budget. For slowly varying $g$, we determine the exact exponent of linear regret deviations on two-armed Gaussian instances with common variance and establish a matching lower bound among policies satisfying the same expected-regret budget on every such Gaussian instance. These quantitative guarantees also cover the greedy variant obtained at zero EL radius. A fixed positive radius introduces local optimism while preserving the leading asymptotic regret. We establish coupled pathwise dominance over the greedy variant in two-armed bandits with a deterministic suboptimal arm. Experiments demonstrate reductions in prolonged suboptimal allocation compared with $g$-Forcing on challenging instances.

Tue 13 OctMachine Learning
The gist
Making choices based on unpredictable rewards is tricky, especially when you don't know how big or rare the rewards might be. The authors created a method called EL-F that learns reliably over time without needing to know reward sizes or details about their variation. Their method limits bad outcomes even in short runs and adapts well when exploring options. This work helps balance trying new things versus sticking to the best choice in uncertain situations.
Open → 2610.18055v1

Regret bounds reveal effects of feedback in adversarial bandits

m-Set Adversarial Bandits with Winner Feedback

Abstract: We show upper and lower bounds on the regret of $m$-set adversarial bandits for different utilities (winner reward or sum of rewards) and feedback models (winner index, winner reward, sum of rewards, and their combinations). By comparing to standard bounds for combinatorial and MNL bandits, our results reveal how subtle changes in the setting can have a dramatic impact on the learning rates. Our main technical contributions are the information-theoretic lower bounds on the regret. Experiments on synthetic data confirm our theoretical analyses.

Wed 7 OctMachine Learning
The gist
This paper studies how well machines can learn to choose sets of options when the outcomes are controlled by an adversary rather than random processes. It looks at how different ways of receiving feedback—like seeing just the winner or the sum of rewards—affect the speed of learning. The authors provide mathematical limits on how much ‘regret’ (or lost opportunity) the learner can accumulate under these scenarios. Their results show that small changes in the feedback design can greatly impact learning efficiency. They confirm their findings with experiments on synthetic data.
Open → 2610.10128v1

Minimax policy improves decision making in bernoulli bandit problems

Multi-Armed Bernoulli Bandits via Minimax Single-Arm Stopping

Abstract: We develop an index policy for finite-horizon Bernoulli multi-armed bandits from minimax solutions to single-arm bandit (SAB) problems. Each SAB problem involves choosing between an unknown Bernoulli arm and a known reward. We show that minimizing worst-case regret of SAB problems over all non-anticipative policies admits an exact semi-infinite linear programming formulation. The resulting stopping policies offer a natural way to compare arms: the higher the known reward against which a policy continues sampling, the more promising the unknown arm. We turn this intuition into indices based on cumulative continuation probabilities, with a monotone adjustment and a reward-shortfall cap. By relating index errors to the regret of single-arm stopping policies, we establish a distribution-free regret bound of $4.45\sqrt{KT}+10.75K$ for $K$ arms and horizon $T$. This bound matches the minimax-optimal regret order established in the literature. The guarantee extends to rewards supported on $[0,1]$ through Bernoulli randomization. We also provide a finite-grid implementation with quantified approximation loss. In numerical experiments, the SAB-based index policy achieves lower worst-case regret than every tested benchmark policy across all evaluated numbers of arms and horizons, while closely matching the grid-based MAB minimax policy in the two-arm setting.

Sat 19 SeptMachine Learning
The gist
Choosing the best option among several uncertain choices is a common problem in fields like online advertising or clinical trials. The authors develop a strategy that focuses on single choices and compares them to known rewards to decide when to stop exploring. Their method guarantees good performance across all possible situations and works well when multiple choices are involved. Tests show this strategy outperforms existing methods, especially when dealing with several options over limited trials.
Open → 2609.22690v1