Neural Contextual Bandits Under Delayed Feedback Constraints
Mohammadali Moghimi, Sharu Theresa Jose, Shana Moothedath · 2025
Read Neural Contextual Bandits Under Delayed Feedback Constraints by Mohammadali Moghimi, Sharu Theresa Jose, Shana Moothedath (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2504-12086.txt.
Introduction
Mohammadali Moghimi, Sharu Theresa Jose, and Shana Moothedath design decision algorithms that learn from late feedback in this two thousand twenty-five paper. Contextual bandits choose actions using side information and learn from the rewards that follow. In recommendation systems and clinical trials, those rewards arrive only after random, unknown delays, because outcomes take time to appear. Their algorithm, Delayed NeuralUCB, explores using an upper confidence bound strategy adapted to neural reward models.
Assuming delays are independent draws from a sub-exponential distribution, the authors derive an upper bound on cumulative regret over a finite horizon. A second variant, Delayed NeuralTS, swaps in Thompson sampling exploration. Experiments on real datasets, including MNIST and the Mushroom dataset, plus comparisons against benchmark methods, showed the algorithms coping well with varying delays. The setting targets real deployments where feedback lag is unavoidable.
Catalog record
| CREATOR | Mohammadali Moghimi, Sharu Theresa Jose, Shana Moothedath |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 41 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2504-12086
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Neural Contextual Bandits Under Delayed Feedback Constraints Mohammadali Moghimi, Sharu Theresa Jose, Shana Moothedath Abstract This paper presents a new algorithm for neural contextual bandits (CBs) that addresses the challenge of delayed reward feedback, where the reward for a chosen action is revealed after a random, unknown delay. This scenario is common in applications such as online recommendation systems and clinical trials, where reward feedback is delayed because the outcomes or results of a user’s actions (such as recommendations or treatment responses) take time to manifest and be measured. The proposed algorithm, called Delayed NeuralUCB , uses upper confidence bound (UCB)-based exploration strategy. Under the assumption of independent and identically distributed sub-exponential reward delays, we derive an upper bound on the cumulative regret over T T -length horizon, that scales as O ( d ~ T log T + d ~ 3 / 2 D + log ( T ) 3 / 2 ) O(\tilde{d}\sqrt{T\log T}+\tilde{d}^{3/2}D_{+}\log(T)^{3/2}) where d ~ \tilde{d} denotes the effective dimension of the neural tangent kernel matrix, and D + D_{+} depends on the expected delay 𝔼 [ τ ] \mathbb{E}[\tau] . We further consider a variant of the algorithm, called Delayed NeuralTS, that uses Thompson Sampling based exploration. Numerical experiments on real-world datasets, such as MNIST and Mushroom, along with comparisons to benchmark approaches, demonstrate that the proposed algorithms effectively manage varying delays and are well-suited for complex real-world scenarios. I Introduction The stochastic contextual bandit (CB) problem has gained immense interest in recent years due to its application in various domains, including healthcare, finance, and recommender systems [ 1 , 2 , 3 , 4 , 5 ] . The CB is a sequential decision-making problem where, in each round, the agent (or decision-maker) is presented with K actions and associated contextual information. Based on the observed contexts, the agent chooses an action and receives a stochastic reward from the environment. The reward generating mechanism is unknown to the agent, and the agent only observes the received reward. The agent’s objective is to maximize the expected cumulative rewards over a specified horizon of length T , or equivalently to minimize the cumulative regret over the horizon. Many provably efficient algorithms have been developed for stochastic CBs assuming linear reward models – linear upper confidence bound (LinUCB [ 6 ] ) and linear Thompson Sampling (LinTS [ 7 ] ) – as well as generalized linear models [ 8 ] , and neural reward models (NeuralUCB [ 9 ] and NeuralTS [ 10 ] ). A common feature of all these approaches is that they assume immediate reward feedback from the environment. However, this is not true in many practical settings. For instance, in an online recommendation system (e.g., Netflix), thousands of movie recommendations are suggested to the user in milliseconds. However, it may take hours or even days for the user to respond to them. The same holds true in clinical trials, where the response time to administered treatments can vary significantly. Recent research [ 11 , 12 , 13 , 14 ] aims to model such scenarios by studying bandits with delayed reward feedback : At each round t , the environment generates a random delay, unknown to the agent, and schedules an observation time for the reward r_{t,a_{t}} corresponding to the action a_{t} chosen at t^{\rm th} round. Theoretically, the presence of delayed feedback introduces uncertainty regarding the information available to the agent at any given time due to missing rewards, which complicates the standard regret guarantees. Consequently, recent works have focused on developing algorithms tailored to the delayed-reward feedback setting. In this context, relevant recent works include [ 15 ] and [ 16 ] , which develop novel algorithms for generalized linear contextual bandits with delayed rewards. These algorithms boost the exploration bonus when the number of missing rewards is large, resulting in regret guarantees that scale as \tilde{O}(d\sqrt{T}+\sqrt{dT(\mathbb{E}[\tau]+M))} , where d is the dimension of the context vector, \mathbb{E}[\tau] is the mean of the unknown reward, and M is a delay-dependent parameter. However, the delay terms in their regret scale with \sqrt{T} . Subsequent work [ 17 ] proposed a simpler algorithm for generalized linear bandits, eliminating the scaling of delay with \sqrt{T} and achieving a regret bound of \tilde{O}(d\sqrt{T}+d^{3/2}\mathbb{E}[\tau]) . This, however, is achieved at the cost of increased dependence of the regret on the dimension d . Here \tilde{O} hides the logarithmic terms. Despite these advances, most research on delayed reward feedback has focused on generalized linear CBs, which are quite restrictive to apply to real-world scenarios with complex reward functions. Neural CBs that leverage the strong representation power of deep neural networks are better suited for modeling complex reward functions [ 9 , 10 , 14 , 18 , 19 , 20 , 21 ] . In this work, inspired by [ 16 ] and [ 17 ] , we introduce new neural CB algorithms that can efficiently handle delayed reward feedback. The following are our main contributions: 1. We propose a Delayed NeuralUCB algorithm and its variant Delayed NeuralTS algorithm for neural CBs with delayed reward observation. 2. For the Delayed NeuralUCB algorithm, we derive a novel upper bound on the cumulative regret over T -length horizon, that scales as O(\tilde{d}\sqrt{T\log T}+\tilde{d}^{3/2}D_{+}\log(T)^{3/2}) , under the assumption of independent and identically distributed sub-exponential reward delays. Here, \tilde{d} denotes the effective dimension of the neural tangent kernel gram matrix, and D_{+} depends on the expected delay \mathbb{E}[\tau] . Importantly, the impact of delay does not scale linearly with T . 3. We conduct extensive experiments and compare our approach against multiple benchmarks on real-world MNIST and Mushroom datasets with various delay distributions. The results demonstrate that our proposed algorithms effectively handle different delay scenarios. Organization: We introduce the delayed reward feedback model for neural CBs in Section II . Section III introduces the proposed Delayed NeuralUCB algorithm and derives an upper bound on the cumulative regret. Section IV discusses the proof of the regret bound. Section V introduces Delayed NeuralTS algorithm and provides numerical experiments evaluating the performance of our proposed algorithms. Finally, we conclude in Section VI . II Problem Setting In this section, we first introduce the neural CB setting and then detail the delayed feedback environment under study. II-A Neural Contextual Bandits Consider the stochastic K -armed CB problem. At each round t\in[T] , the agent observes the context consisting of K feature vectors \{\mathbf{x}_{t,a}\in\mathbb{R}^{d}:a=1,\ldots,K\} corresponding to each of the K arms. Based on the observed context, the agent selects an action a_{t} and receives a reward r_{t,a_{t}} . We assume that the reward is generated as, \displaystyle r_{t,a_{t}}=h(\mathbf{x}_{t,a_{t}})+\xi_{t}, (1) where h(\cdot) is an unknown mean-reward function satisfying 0\leq h(\mathbf{x})\leq 1 , and \xi_{t} is a zero-mean noise. The goal of the agent is to design an action-selection policy that minimizes the cumulative regret over T rounds, \displaystyle R_{T}=\mathbb{E}\Bigl[\sum_{t=1}^{T}r_{t,a_{t}}-r_{t,a_{t}^{*}}\Bigr], (2) defined with respect to the optimal action a^{*}_{t}=\arg\max_{a\in[1,\ldots,K]}h(\mathbf{x}_{t,a}) that maximizes the mean-reward. Neural contextual bandits [ 10 , 9 ] estimate the unknown mean reward function h(\cdot) in Eq. ( 1 ) using a fully connected neural network with depth L\geq 2 as \displaystyle f(\mathbf{x};\boldsymbol{\theta})=\sqrt{m}\mathbf{W}_{L}\sigma\Bigl(\mathbf{W}_{L-1}\sigma\Bigl(\ldots\sigma(\mathbf{W}_{1}(\mathbf{x}))\Bigr)\Bigr), (3) where \sigma(x)=\max\{x,0\}