Learning Personalized Ad Impact via Contextual Reinforcement Learning under Delayed Rewards
Authors: Yuwei Cheng
Zifeng Zhao
Haifeng Xu
Venue: NeurIPS 2025 poster ()
Keywords: online learning; Contextual Markov Decision Process; maximum likelihood estimation; delayed reward; reinforcement learning; auto-bidding
Primary area: theory

Abstract: Online advertising platforms use automated auctions to connect advertisers with potential customers, requiring effective bidding strategies to maximize profits. Accurate ad impact estimation requires considering three key factors: delayed and long-term effects, cumulative ad impacts such as reinforcement or fatigue, and customer heterogeneity. However, these effects are often not jointly addressed in previous studies. To capture these factors, we model ad bidding as a Contextual Markov Decision Process (CMDP) with delayed Poisson rewards. For efficient estimation, we propose a two-stage maximum likelihood estimator combined with data-splitting strategies, ensuring controlled estimation error based on the first-stage estimator's (in)accuracy. Building on this, we design a reinforcement learning algorithm to derive efficient personalized bidding strategies. This approach achieves a near-optimal regret bound of $\tilde{\mathcal{O}}(dH^2\sqrt{T})$, where $d$ is the contextual dimension, $H$ is the number of rounds, and $T$ is the number of customers. Our theoretical findings are validated by simulation experiments.

Learning Personalized Ad Impact via Contextual Reinforcement Learning under Delayed Rewards*
Yuwei Cheng Department of Statistics University of Chicago Chicago, IL 60637
Zifeng Zhao
Mendoza College of Business University of Notre Dame
Notre Dame, IN 46556 zzhao2@nd.c edu
cuwerichenguuchicggooooo edu
Haifeng Xu
Department of Computer Science and Data Science University of Chicago
Chicago, IL 60637
haifengguuuuchicagoooo edu
Abstract
Online advertising platforms use automated auctions to connect advertisers with potential customers, requiring effective bidding strategies maximize profits. Accurate ad impact estimation requires considering three key factors: delayed and long-term effects, cumulative ad impacts such reinforcement customer heterogeneity. However, these effects are often nol jointly addressed in previous studies. To capture these factors, we model ad bidding as Contextual Markov Decision Process (CMDP) with delayed Poisson rewards. For efficient estimation, we propose two-stage maximum likelihood estimator combined with data-splitting strategies, ensuring controlled estimation error based on the first-stage estimator's (in)accuracy. Building on this, we design reinforcement learning algorithm to derive efficient personalized bidding strategies. This approach achieves a near-optimal regret bound of 2 dimension, H the number of rounds, and T is the number of customers. Our theoretical findings are validated by simulation experiments.
fatigue, and
where is the contextual
Introduction
E-commerce is expanding rapidly worldwide, with online sales expected to constitute 23% of total retail by 2027, supported by a 14.4% annual growth [ITA 2025]. This growth has made digital advertising inevitable, empowering tech giants like Google, Meta, Microsoft, and Amazon, which leverage automated auctions to connect advertisers with customers. Auto-bidding, where platforms handle bid placement behalf of advertisers, has grown significantly because of its simplified interaction for the advertisers and improved performance thanks to real-time optimization [ggarwal
al. 2024 Google Ads Support 2025 Facebook Ads 2025 Mierosoft Ads 2025 Amazon Ads
2025
Given its importance, it is crucial to develop effective ad bidding strategies.
Developing effective bidding strategies requires accurately understanding advertising impacts. Psy- chological studies have long shown that advertising has a delayed and long-term impact on consumer beliefs and attitudes, ultimately shaping purchasing behavior over time [Vakratsas and Ambler 1999
"This work is supported by the AI2050 program at Schmidt Sciences (Grant G-24-66104), Army Research Office Award W91 199-33F--311--00 and NSF Award CCF-2303372.
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

Lewis and Wong 2022, Sakalauskas and Kriksciumiene, 2024]. significanlly across individuals. Observational studies reveal substantial heterogeneity based on demographics, platform usage patterns, and census data [Liu et al. 2019 Gordon et al., 2019). These insights recommend personalized e-commerce advertising, suggesting platforms should leverage customer data to target high-value users and optimize bidding strategies tailored to diverse behavioral profiles [Sakalauskas and Kriksciuniene 2024]. Additionally, the impact of ads also depends on their cumulative effect: while repeated exposure can strengthen brand recognition, it may also lead to ad
Advertising effectiveness varies
a subtle trade-off that is often overlooked in "learning to bid" literature
PPechmann and Stewart 1988
Lane 2000
You et al. 2013 Bell et al. 2022, Guo and Jiang 2024).
Limitation in recent work. However, these insights are not fully reflected in current algorithmic designs. The problem of "learning to bid" has been widely studied, with most prior work modeling it as a (contextual) bandit problem that assumes immediate rewards, such as click-through rates, which prioritizes short-term customer engagement [Weed et al., 2016 De Haan et al. [ Ren et al., 2017 Feng et al. 2018 2023 Han et al., 2024 Zhang and Luo 2024). This approach, however, neglects the delayed and cumulative effects of advertising on consumption, potentially leading to incentive misalignment [Deng et al. 2022]. This misalignment is further exacerbated by the rise of auto-bidding systems, where platforms automatically manage bidding decisions on behalf of advertisers. While platforms typically optimize for engagement-bang based metrics, advertisers ultimately care about long -erm revenue growth via production conversion Recent work has therefore begun to emphasize metrics like target return on ad spend as a practical alternative (Wang et al. 2019 Aggarwal et al. 2024] and design bidding strategies which account for delayed and cumulative effects of ads. Recently, Badanidiyuru et al. [0023 models the long-term causal impact of ad impressions using Markov Decision Process with mixed and delayed Poisson rewards. However, this approach assumes homogeneous treatment effects across users, overlooking the importance of personalization, a crucial factor in advertising effectiveness. To the best of our knowledge, no theoretical work jointly addresses all three aspects-delaye effects, cumulative impacts, and heterogeneity-in modeling ad effectiveness and designing bidding algorithms, potentially due the modeling complexity and difficulty in estimation.
Our contribution. To address this gap. motivated by the initial proposal of Contextual Markov Decision Process (CMDP) (Hallak et al. 2013 to model customer behavior during website inter- actions, we model auto-bidding CMDP with delayed Poisson rewards- using context to capture personalized ad impacts and states to capture ads cumulative effects. For effective estimation, rather than fitting all model parameters simultaneously using a single giant likelihood function, we introduce a novel data-splitting strategy and develop a two-stage maximum likelihood estimator that ensures controlled estimation error in the presence of delayed impacts. Based on this efficient online esti- mation oracle, we design a reinforcement learning algorithm to solve the CMDP with near-optimal regret of Ō (dH+2VT) where d is the contextual dimension, H is the number of rounds, and I' is the number of customers. Finally, we perform simulation studies which validate our theoretical findings.
2 Modeling Personalized Ad Impact by CMDP with Delayed Rewards
Notation. For a positive integer T" we denote [T] = {1, .., We use standard asymptotic notations, including O-), 92()). and e(.), as well as their counterparts Ö(-). $2(-), and é(-) to suppress logarithmic factors. The symbol e represents the base of the natural logarithm. The Mahalanobis norm is defined as ||x| x = vx Σx. || ll2 represents L2 norm. For vectors x and y. we use (x,y) and x interchangeably to denote their inner product.
T}.
To address the complexities of advertisement impacts on product conversions, we model online ad bidding as Contextual Markov Decision Process (CMDP). This framework captures the three key impacts discussed in Section [ and allows transitions and rewards to depend on context x;- personalized information of customer t, supporting dynamic and personalized bidding. While incorporating x, directly into the state is possible, it greatly enlarges the state space and complicates learning (Levy and Mansour 2023). Instead, we adopt a CMDP formulation-coome applications- that keeps the state compact and treats context as auxiliary information (Hallak et al. 2015). preserving both efficiency and personalization. Our analysis focuses on ad platforms that bid on behalf of advertisers. We use "ad platform" and "learner" interchangeably.
in user-driven
We defer more detailed discussion of the "learning bod literature Appendix A.I

---

Mathematically, a CMDP is defined as the tuple (X,,,A,,) where X' S R represents the contextual feature space, S denotes the state space capturing customer ad exposure history, and A is the action space for ad bidding strategies. The mapping M assigns each context x to Markov Decision Process (MDP), M(() = (S, A. Px, RR, St, H), where the state transition probability px and reward function Rx depend on x. Si is the initial state. H. represents the maximum number of customer-learner interactions with details in the context of online bidding as below.
Definition 2.1 (State). The state of customer at round h, denoted as S) = [S% S2.2 encodes information about the two most recent ad exposures. Specifically, let G,,1 represent the round of the most recent ad impression, we set 1 h Gh,1 which captures the time elapsed since that impression. Similarly, let G2 denote the round of the second-to-las ad impression, we set , G - representing the time interval between the two most recent impressions. S, E H4 = foo, 1....... .,, H - 1} and Sh.2 E H2 = {-00, 1,2.,,,...... 1.2...., H - 2]. The interpretation of 0o and -0o is deferred to Remark 2.3
Assumption 2.2 (Observation). The expected product conversion rate n at round h for customer with context follows
dg: x ss
if of =0
14h
n Xi S
otherwise.
The observed product conversion yi follows Poisson distribution, i.e. yt. Poi(())) dsp,, represents the delayed advertisements impact, S E H1 = 1, H - 1}. of indicates the bidding outcome for customer t round h. of = 1 if the bid is won and oj 0 otherwise.
Remark 2.3. If customer has prior ad exposure, the state is S = [oo, -oo Specifically, when no advertisement has been successfully displayed, product conversion y/ ~ Poi((()) where H = X -_.. Here, x 0_ represents the natural demand in the absence of ads, which may vary with context X₁ to capture factors such as income, preferences, tastes, and scasonality [Manandhar 2018). We set dx = 1 to avoid identifiability issue. If the learner wins the bid, yi. ) ) with ji = x 2x. where Ox captures the effect of first-time ad exposure. It is possible to generalize the linear modeling of the expected product conversion rate to a more flexible form, i.e., M hiy (.z). For example, heg,, may be modeled as state-dependen neural network, though this would come at the cost of sacrificing theoretical guarantees. We refer readers to Appendix A.2 for a detailed discussion.
As illustrated in Figure 1 if no new advertisement is displayed at round h, the impact of the previous ad shown at round G carries over, with a delayed and long-term effect governed by dn-Gk,1 depending
last ads impression time
time horizon
on the time interval h G% This delayed factor allows ad effects to span multiple rounds, enabling delayed conversion peaks, as di is not restricted to be less than 1. This results in an expected product conversion of d dn x, 00.,,--;, (Assumption captures the impact of the shown at Gh,, which affected by its most recent predecessor at G%,22- In contrast, if new ad is successfully displayed at round h, its effect overrides the previous one, but itself influenced by the most recent prior impression at round Gh,,1 The resulting impact is modeled by O 0 leading to an expected conversion of x 0 On-Gt,a"
Ga
sacond ads Impression time current round
C
Figure 1: Illustration
2.2p. where Oct,, - -
A natural question arises: why does the cumulative advertising impact depend only on the most recent display, rather than the entire history of ad exposures? This modeling choice is motivated by the recency effect, a well-documented cognitive bias in psychology and marketing (Murphy et al. 2006 Chatheeld [016)] [Phillips- Wren al., 2019]. suggests that individuals tend to place greater weight on recent experiences when making decisions. This phenomenon is especially relevant in advertising, where exposure timing significantly affects consumer behavior [Chatfield] 2016). and underlies practical approaches like Google's attribution models [Google Ads Attribution, 2025 which uses last-touch heuristics that prioritize recent ad exposures. fact, our state formulation is very flexible and readily accommodates an enlarged state space. It supports a broad class of CMDP
3

---

formulations for Os. where S encodes domain knowledge about ad effects, and remains compatible with our proposed learning algorithm. For example, we believe that all past ad exposures contribute to customer behavior, we can easily extend the state to include Sy : n/ where ni, is the total number of successful ad displays in the past. We refer readers to Appendix A.3 for detailed discussion of the flexibility of our state formulation.
The bidding outcome of, depends on both learner's bid ai, and the competitors' bids. The bidding space is given by af, [0, BAl, where B is the maximum allowable bid. ai, 0 indicates that the learner opts out of the auction. At each round, the learner submits af, and wins if its bid exceeds all competitors' bid. The probability of winning by af, is shown below.
Definition 2.4 (Transition). For a given bid amount ai. the probability of winning the auction, denoted as P(o = 1), is modeled by Fi xt), where Fr : [0. BA] x X - [0, 1] represents the cumulative distribution function (CDF) of the Highest Other Bids (HOB).
Remark 2.5. Given the current state S% = [ S%.21 and bid ai, the next state transitions according
to Fr ( xx). With probability Fr. (a), xt), the bid is successful, and the next state is S/
[1,1) Otherwise, the bid is lost, and the state transitions to S = [ + 1, 1,
This CDF, Fn (a),, of HOB captures the competitive bidding environment by modeling both context x, and time h. allowing for round-to- variation from changing competitors and context- consider full information feedback driven bid adjustments. In line with standard practice,
setting, where the realized HOB mi, is observed by the learner regardless of the bidding outcome [Ces-BBianchi al., 2014 Feng et al., 2018 Zhang et al., [2022] BBadanidiyuru et al. 2023 This setting is practical since bidders can always access the "minimum- bid-to-win feedback [Google] Developers 2024). Also, ad platforms inherently know realized bids for their auto-bidding algorithms.
We assume mi follows a lognormal distribution, a common modeling choice in the literature for
advertisement auctions [Laffont al.. 1995 Wilson 1998 Smith al. 2003 Skitmore 2008 Mallesteros-Pérez and Skitmore 2017] (Assumption 2.6). resulting the probability of winning with (x,, (5))//n))))))))))))))))))) where & denotes the CDF of the standard normal distribution, Br. E IR represents the highest willingness to pay for displaying ads from other competitors, capturing the competitiveness of the environment, while dn reflects the associated variability.
bid ai, (a xx) ([oog((a)
Assumption 2.6 (Lognormal Distribution of HOB). log(m);) ~ (((x,,))).. Ba),
In second-price auction, the format we study, the winning bidder pays the second-highest bid, with payment given by ph (af, xx) = at, - Fi (a) x
Fi (U, X dv.. This format is standard in both industry and research [Cooper and Fang 2008 Weed et al., 2016 Zhao and Chen 2019). and our analysis extends to other single-item auctions without entry fees, such as first-price auctions. To bid effectively, the learner must balance the probability of winning, the incurred payment, and the expected product conversion. Without loss of generality, we normalize the value of each unit of product conversion to v = 1, leading to the following definition of the expected reward.
R2, (Sh, ai x.) = dsg, (0 s0st.. x1 - (a x.)) + (10 st xx) Ph (a x. xx)) (a xt).
By these formulation, in the context of online bidding, the tuple (X' S, A. px, (Rt (st, af,- 1. St. probability distribution of states 5% induced by (Fa(- x, x JJJnniin We direct reader to Appendix A.4
H) is CMDP (Fact 2.7
Appendix D.Ip. px: is the joint
for an illustration example for modeling online bidding as CMDP.
Fact 2.7. S,, (R) (S, a x)) St. H) is a CMDP.
2.1 Learning goal: regret minimization
The learner interacts with T customers over H rounds, receiving context information x, for customer
t. The learner begins without prior knowledge of the product conversion parameters θ = (0) hew U {di Jen [ nor the transition Jx. = {Fu( x We assume θ and transition parameters heete U (ox]eejH] are bounded. The context space X' is also bounded, with no distributional
P Due to the special meaning of oc and -oo, we define h - oo = co, and h oo - (-oo) = oc.
"H Hi U H2

---

assumptions on the arrival of X₁. is small positive constant, which ensures that displaying an ad always yields non-zero (expected) purchase quantity (Assumption 2.8).
Assumption 2.8. There exists positive constants b, B2, Bg, Ba, Bg, such that |xx S Bgg and 0 x; 2 b, Vt e (T), vZ H. |0:122 I Bo, VI E H. di E [0, Bal, vI H1, and ||, 1|2 S B3, oh S o, vh H
The learner's objective is to minimize the cumulative regret over I customers with regret defined as:
Regr Σ OPT (O,,,, FK:) ExI.... Sy
R O F,F%)
(1)
The expectation is taken over the policy Te S S X + [0, BA] generated by the algorithm g employed by the learner. We define OPT(O, x,, Fxi) as the optimal expected utility achievable for a customer with contextual features over H rounds, under the true parameters O and the distribution FKx, The reward collected by the policy Ti over H rounds for customer i, denoted as R(T; X4, θ FK)), denoted by R (Tz; X1, FX:) = - 1Σ R% (5), Te(S), x()].
3 Algorithm Design
In this section, we introduce design principles for solving CMDPs with delayed Poisson rewards. The proposed algorithm (Algorithm I consists of three main stages: exploration, exploitation, and estimation, with the estimation stage playing central role.
The estimation stage contains three key components. First, ridge regression [Abbasi- Yadkori et al. 2011] combined with two-stage variance estimators is used to estimate the transition dynamics Jxx, handling potential adversarial arrivals of x,, Second, variant of online Newton estimator [Xue et al., 2024] is employed to estimate the instant advertisement effects [0: Third, a novel two-stage maximum likelihood estimator (TS-MLF) developed to estimated the delayed impacts (di (d))te
The key challenge in online estimation is that a naive approach-ssmmutaneonn updating all parameters by maximizing a joint log-likelihood (())-is infeasible due to two main issues. First, the log-likelihood function C(O) is non-concave in O, making it difficult to ensure a unique solution. Second, the score equations Ve((O)= lack closed-form solutions, rendering direct analysis intractable. These challenges motivate the development of the estimator, TS-MLE, which efficiently estimates delayed effects while maintaining computational tractability.
estimating and
The core idea of the TS-MLE is to divide the estimation into manageable steps. Intuitively, the estimation error, ||0; - O1l12, is small, O can then be treated as a close approximation of the true parameter 0j. Based on this approximation, maximum likelihood estimator d, can be constructed, ensuring that the estimation error for di remains small. This approach is feasible because the conditional log-likelihood [((d)) hIeH 1f is concave in (di Iee, H, (Eqn. (2), and both its gradient V (di))e L (Eqn. 12) and the solution to the corresponding score equation V (di)ee L = 0 (Eqn. (3) are straightforward to compute.
To control the estimation error of di is crucial to ensure that this error depends only on the error in 0, not vice versa. This prevents feedback loops between the estimation errors of d; and 0, which would otherwise complicate mathematical analysis and make the estimation process intractable. To achieve this, we employ a carefully designed data-splitting strategy, where separate data subsets are allocated exclusively for estimating O and di, ensuring their errors remain independent.
To achieve this separation, we introduce two datasets, W., and Dt,,. I. which share a common structure but serve distinct purposes (Def. 3.1). Both datasets focus round h for customer / where the most recent bid win occurred / rounds before the current round (S), = l). The key difference lies in the parameter being estimated. W.. includes rounds that observations {yf Jew.., with mean (0,, xx). Thus this datasets is used to estimate 6,, as they depend solely on 0, D,,, contains rounds that observations {vf, heeD, with mean di (0s; xx). This datasets is used to estimate di because
they depend solely on the unknown parameter di when (0.)e are given. This ensures that the estimation error of d, depends on 0₁ while the estimation error of O remains independent of di.
5

---

Definition 3.1. For customer t, we define two datasets: Wi, = {h|Sh, = 1, 1, = 1} and
D,,, Si of 0), for E HA--oo.. We define Wt,- 6,-0 (h|S),1 00, oj 0) for the
estimation of f -cc The collection of observations across the first customers are Wi { s. Is1s and D = (Da.)s=1- The size of D is given by Nr.1 = D
Taken this together, the log-likelihood di up to the first customers as:
(yy dr; 01) = E Σ yn log [dxx, (ix_0s;n1 0s
dix, 0
(2)
am NED
Differentiating the log-likelihood with respect to di, setting to zero, and solving for di, results
dt E.=1 EneD., Vi
(3)
E EnED,, (0 S
In the online setting, dj estimates di of customer i, analogous to 0f. Instead of using the most recent estimates 1'= as the first-stage input for estimating d;, we leverage {0 2/ ) progressively updated estimate of the advertisement's 's impact across customer arrivals. This novel design is motivated by the observation that the estimation error of 0% instead of S% in the direction of x, is well-controlled. Further details, including the confidence region Dj (line 2 of Algorithm are provided in Theorem 4.1 and its proof.
Algorithm Online Contextual Reinforcement Learning with Delayed Poisson Reward input d, T, H, b, Br, Ba, Ba, A, 5, P,
for = 1 to T do
2: Obtain the context x2 for the arriving customer t
if S (H 1)ng then
4: /* Exploration */ Compute
5:
6: ir H, set a = O, vh E [H]; else set a aj.; BA. and at, 0 for vh + 1,/+1
7:
for h = 1 to H do observe yh. mf, then update 33 by Eqn. (5) and 0f by Eqn. (6)
8:
else
9:
/* Exploitation */
Update n. arg maxx maxsec, A[ 0, fxz:
10:
11:
for h 1 to H do
12:
Observe Sj and take action at, = Te (S%, xx)
13:
Observe 0/,, m/. and yi and update 3% by Eqn. 5 and of by Eqn. 66)
end for
15:
end if
16:
1*
Estimation $/ for / E H. do
17:
18:
Update dataset Wi. D by Def. 3.1
19:
if W., is nonempty, compute 0j and Cf by Algo. 3 else set 0 = = and C C
20:
if Dr.1 i nonempty, compute d and Df by Algo. else set de di and DJ D
21:
end for
Set C. = (0) (0, e C E DIl.Vl H)
23:
end for
Remark 3.2 (Key Tuning Parameters for Algorithm D.. The input parameters d, T' and H are structural components of the CMDP. The quantities b, Bz, Ba. B.,, B are defined Assumption 2.8 The tail probability 8 determines the confidence region for 3r and d, and serves as an input for Algorithm 3 and Algorithm The truncation threshold I2 used to handle heavy-tailed distributions, is defined in Eqq (T0) and appears Algorithm The parameter 7, defined in Lemma 3.3 serves as a weighted estimation error bound and is used Algorithm 2 The exploration stage guarantees a minimum

---

number of observations to ensure reliable estimation. Specifically, the threshold ny is given by 32 log LHT)
cB.B, Ba which guarantees sufficient observations in Wi and Dý, ensuring [Wi] 24
and No,1 = Di 2 By for all E H. in all subsequent episodes after the exploration stage.
The estimation of dj depends on accurately estimating 0-- Using observations y from Wi, the problem reduces to efficiently estimating O from Poisson data. To achieve this, we adopt the
Confidence Region with Truncated Mean approach (see Algorithm and and Appendix [B), introduced by Xue et al. [2024). This method utilizes a variant of the online Newton estimator, given by:
arg min 12 0 lI: + (0 (0-0) TV.
(4)
11 Bg
Vi V + X with Vi initialized as the identity matrix La- vi((t-1) (-5% (x4) 0f Xz, The truncated observation y is defined as y%. = - =x=llxil( y/
This truncation mitigates the impact of extreme values in y by setting outliers to zero, a technique originally designed for generalized linear bandit problems with heavy-tailed data.
By Lemma 3.3 the weighted estimation error ||0: probability.
0 remains well-controlled with high
Lemma 3.3 (Theorem 1 in Xue al. (0024). ) Given I E H. with probability least 1 8, 0 defined in Eqn. satisfies
|0: O I 7, Vt 2 0, where 7 B9
Bg Ba) log log
42
(1
2d
BB g + 48dB, Be log (1
2d
T
To estimate the transition dynamics Fr. we estimate Br by Eqn. set 1 1.
5
Without loss of generality, we
3% = - (xxx
+ Ald
Σ X log(m)))
(S)
The variability ohe similar to df. estimated based on the first-stage estimators {,6])... (Eqn. (6)) We use 1 instead of 3 to control over estimation eтror in the direction of x, (details in Appendix C.2).
(ogg(m)) x_ xx
(6)
In addition to estimation, the exploration period aims to gather sufficient observations for di to ensure quadratic tail decay of Poisson (Remark 3.2p.
After exploration, the algorithm enters exploitation, selecting actions via the greedy policy m. to maximize rewards within the confidence region. is computed via dynamic programming with time complexity Poly( H, [S], B/cc) when discretizing the bidding space for an e-optimal solution (detail in Appendix A.5). ). By balancing exploration and exploitation, Algorithm aachieves near-optimal performance, formally proven in the next section.
Algorithm 2 Two-Stage Maximum Likelihood Estimation
input datasets Dj. (xx)%= $; 1.-1 and parameters B., Bo, BR, d, T, H,
1: Update the two-stage estimator dj by Eqn. (3)
2: Compute Dj- { de [0, Ba] d del
48 Bay d log 1+ 2a h+ 20 Ba log(2/8)
by/Nei
output (d) D1)
4 Analysis of Near-Optimal Regret Bound
This section demonstrates the efficiency of the TS-MLE (Theorem) 4.1 and analyzes the near-optimal performance of the proposed Algorithm TThorem 4.2
7

---

T Theorem 4.1 (Confidence Region for di,, Let 5 2 THH and No. 2 my. With probability at least
1
1 6, the estimation error |dj del, with dj defined Equ. ( is bounded by:
|dj - del 4H log 2
Be log
No,
is as defined in Lemma 3.3 and nu defined in Remark 3.2
Theorem 4.1 shows that the estimation of TS-MLL is bounded by O(1 v NT.). where Ni, (Def. B.T) is the total number of observations used to estimate dj. This result demonstrates the efficiency of the estimator, achieving near-optimal parametric convergence rate [Rao 1992].
Proving the near-optimal convergence when data are collected from a complex CMDP with delayed observations requires precise understanding of the sources of estimation error and refined analysis to control them. As discussed in Section 3
the core idea for estimating di is to use observations that are "purified" with respect to d₁. In particular, we construct di using only observations ([v% JeD.. V== where y Poi(d (!st.. xx)). Then, to analyze how the estimation error of TS-MLE depends on the strst-stage estimators 0z we decompose ldž dil into two parts: the error by the randomness in Poisson observations (Term A in Eqn. () and the cumulative estimation enror from the first- stage estimators (Term Eqn. 8) Th in Term A has sub-exponential distributions, specifically, SubE(ed; x 2 1) (Lemma D.I since y dix] 0s 0sg,, + mh To control the heavy tail of Term
A, we show that P(Term A > <) S 5, where V
Be log(z)) The exploration phase of 22 / 6'N,1
Algorithm D ensures No.1 2 Tu providing sufficient observations to make small enough to have faster convergence.
E.s1 EnED., m
Ba
|d - dil
Σ
(05r.. - -03
(8)
Ei=1 EnED., (0
x2)
Noa
#=1 hED
Temm A
Term
Controlling Term B is essential for bounding (dj dil. Unlike traditional second-stage estimators, which typically plug in the most recent estimates S we instead use 0% @ as its estimation error
better controlled the direction of x,, Specifically, let rf. = 1(0 s Osp,a) x,l denote this
directional estimation error. By the Cauchy-Schward inequality, we have rī < |10| Or lrllv; |xx [>x|l((;;)-,, where l' = S Letting ?p- ||0g - 0,11,; Lemma 3.3 guarantees that n/ S holds with high probability for all and l'.
To analyze the growth the directional estimation error rí for each E H over time, we ap- ply recounting techniques. Define the dataset F := [4|S%, = I, S, = o' 0}. which partitions Dz, by Si.2. the time interval between the two recent ads impression. This partitioning ensures EVER, |F s.rl DDall- We then bound the total directional error as: E' ExED,, 1(0%, 0s% xx, /Nu. E. EnEFY
a.21 (r2)), Let naP F where n4. S H. The total count across all partitions satisfies Et= EveRs "s,"" Nr.- We further bound the error as E ne,r' min (I|x, (l( ,,,;)),,,,,, 1). Applying the Elliptical
Potential Lemma Abbasi-Yadkori et al. 2011]. we obtain 2H No, log (1 + 1 Finally, by applying union bound account for the simultancous occurrence of Term and Term B, establish Theorem 4.1 (details in Appendix C.T).
Building the efficiency of TS-MLE, now show that the regret of Algorithm is nearly optimal, as established in Theorem
Theorem 4.2 (Nearly Optimal Regret), For any 8 2 T3, with probability at least Regr
incurred by Algorithm
is OdHH2 Tlog( TH log(1 + 22 ))-
8

---

Theorem 4.2 shows that, with high probability, Algorithm achieves regret bound of ((VT) Given the (?( ((VT) lower bound for CMDPs with even known transitions [Levy and Mansour 2023
this confirms that Algorithm iss nearly optimal in T. As discussed earlier, the key challenge in designing an efficient reinforcement learning algorithm for CMDPs is developing
online estimation oracle that handles long-term Poisson rewards under potentially adversarial arrivals of contextual X without relying on distributional assumptions. This improves upon prior work (Modi and Tewari 2020 Levy and Mansour 2022] 2023 Levy et al. 2023], which is limited to instantaneous rewards and cannot capture long term effects in CMDPs, addresses long-term rewards but fails to account for the heterogeneous effects of x, (Badanidiyura et al. 2002]. Even with TS-MLE, establishing a nigh-probability regret upper bound for Algorithm is nontrivial and requires careful analysis. We provide a proof sketch below, with detailed arguments in Appendix
The proof begins by decomposing Regr into four terms. In Eqn. () Term (i) equals E. O )) - x,, F and Term (iv) EEETT R(Te: X θ Fr
R(TE; Fx))), capturing the cumulative regret due to transition error, arising from the discrepancy between F= and P Term (iii) Σ OP x,,
which accounts for decision error resulting from imprecise estimates of the model parameters θ = {0: JIEH U {de)E Thus, accurate estimators of fx: and θ lead to
B(ΣL> R( X O, Frr
low cumulative regret, as shown jointly by Lemma 4.3 4.4
Regr V T(logT) + Term (i) Term (ii) + Term (iii) + Term (iv)
(9)
Lemma 4.3 (Term (i) Upper Bound), For ā 2 1/T4, with probubility at least 1 - 6, Term (i) in
Eqn. 9 is bounded above by VT /og((1 log(1 + TT/d))-
Lemma 4.3 provides a high- probability upper bound for Term (i). The proof firstly uses the simulation
lemma Kearns and Singh [002] to bound Term (i) by the cumulative estimation error in the transition
dynamics, Ei= sup, sup, FF (b, x.) - Fi (b, xx)]. which depends 1.8% -Bp. and (( -o A high-probabilityy bound is then derived for these estimations errors, with (( of shown to follow sub-exponential distribution. To ensure quadratic tail decay, we set 5 2 1/7 _ A similar
analysis applies to Term (iv), which is bounded by O(dH² VT /log((( + T)/5) log(1 + T/d)) with probability at least 1 - 1/T". Details are in Appendix
C.2
Lemma 4.4 (Term (iii) Upper Bound). With probability at least 1 28, where ö At. Term (iii) in Eqn. 9 is bounded by OH2 /CT log(4T log(1 + T/2d)).
Lemma provides a high-probability bound for Term (iii,, which can be decomposed into two parts: the cumulative estimation error of of. which is DT E( 1(00-1 0t
@t11 - xn)) + ET_ BO K0 - Ôt 5
x)))
ΦC-1 -0s -ss xx)l) and the cumula-
st.
Sh,2
tive estimation error of di, specifically, DT= EE
H
7 R..1
d==1
+ d=a1
dst D). Here,
6 == arg maxeec.. R(mxi O, Pr Applying Lemma 3.3 and Theorem 4.1 together with a union bound, yields the high-probability bound for Term (iii) (Appendix C.3
Meanwhile, in Eqn. D. Term (ii) = Σt= OPT(O, xt, xt, Fx:))))))) ΣT_ OP, x Ex, mea- sures the gap in regret between a chosen point and the optimal point within feasible set. Lemma 4.5 proves @ E C, for all t 2 t with high probability, ensuring that Term (ii) can be negative with high probability. Combining these results, we conclude that, with probability at least fa. the overall
regret Regr is OdH?2 Toll TH log(1 + ))
Lemma 4.5 (Confidence Region of θ). With probability at least 1 1-6 with 8 2 Gs. θ E C, V
5 Experiments
We conducted experiments, which leads to two key findings: first, our algorithm achieves near-optimal regret scaling of /T, and second it consistently outperforms several strong baselines, including aggressive bidding, passive bidding, and random bidding strategies, with definition shown below.
'ee have Hn + 1 and regret incurred in the exploration phase is ("o

---

Environment Setup. We simulate second-pric auction with horizon H = 3 (a realistic setting since advertisers typically show ads only few times per user), context dimension d' 2, and T= 20,000 sequential customers. The first 2400 rounds are used for exploration, and the remaining rounds for exploitation. Context vectors x; E RR, as well as parameters di, fr. Th are sampled elementwise from (0, 1}l + 0.1 to ensure positivity, while 0 ~ 50 1)1 + 0.1. Under this configuration, each ad impression yields an average instantaneous reward roughly five times its cost (i.e., the highest other bid). The reward also decays rapidly over time, making aggressive bidding-always winning the impression to optimal and therefore a competitive baseline.
Estimators. We estimate four sets of parameters: 6₁ via the online Newton method (Algorithm 3
with truncation threshold I' = 100,000, bound B, -10, zero initialization, and Vo I. We estimate delay impact di via the two-stage MLE (Eq. (3) using Dr.,, O, and x,; B by ridge regression (Eq.
(5) x= = 1.0); and a via empirical variance (Eq. (
Connection Between Bid, Outcome, and Reward. In our setting, the bidder's action is the bid amount, but due to the second-price auction format, the reward depends only on the outcome-whether the bid exceeds the HOB-not the bid itself. Winning results in paying the HOB; losing incurs no cost. This decoupling allows optimal rewards to be computed from outcomes rather than bids. We leverage this to evaluate both oracle and policy-based rewards. With full knowledge of true parameters, we enumerate all 2 = 8 possible win/loss outcomes and define the oracle reward as the maximum achievable value. With estimated parameters, we compute expected rewards for all outcome sequences, select the best, and evaluate it in simulation. Regret is then the cumulative difference between oracle and realized rewards, reflecting both estimation and decision errors.
Baseline Policies and Regret Comparison. We compare our algorithm against three fixed policies: Aggressive bidding: Always bids above HOB (o, = [1, 1, Il). Random bidding: Samples o, uniformly from all 8 outcomes. Passive bidding: Rarely bids or wins (or = [o, 0, 0)). All baselines are evaluated using the same oracle-based regret metric. Note that aggressive bidding, while competitive, still incurs O(T)) regret since it is non-adaptive.
We ran all algorithms over 20 independent trials. Table I reports the mean cumulative regret (# 0.5 standard deviation) and the fitted regret order (via log-Tog regression). Our algorithm achieves an estimated regret order of 0.37, while all baselines exhibit linear regret, validating
theoretical results and demonstrating the substantial advantage of adaptive learning in ad bidding.
Table 1: Average cumulative regret (+: 0.5 standard deviation) and associated fitted regret order (I
Algorithm 1
Aggressive Bid
Random Bid
Passive Bid
500 1770 [1174, 2379]
228 [121, 336]
1920 [1791, 2049]
4630 [3391, 5869]
5000
8465 [5585, 11345]
2373 [1243, 3502]
19285 [17873, 20697]
46179 [33850, 58508]
10000 8484 [5606, 11363]
4741 [2477, 7005]
38399 [35573, 41226]
92468 [67735, 117201]
15000
8505 [5628, 11382]
7142 [3724, 10561]
57651
[53452, 61849]
138652 [101576, 175729]
20000 8525 [5649, 11401]
9568 [4991, 14146]
76945
[71390, 82500]
184873 [135414, 234332]
7 0.37
1.0
1.0
1.0
Discussion and Limitation
In this paper, we model ad bidding as a CMDP, presenting a unified framework to address delayed impacts, cumulative effects, and individual personalization. We designed a near-optimal algorithm us- ing a novel two-stage maximum likelihood estimator to effectively handle delayed rewards. However, several important directions remain open for future research. One promising extension involves incor- porating budget constraints, a critical practical consideration in real-world advertising. Developing constrained optimization algorithms for CMDP with delayed rewards is highly non-trivial and will be explored in future work. Although our work validates the theoretical insights through experiments, implementing and evaluating the proposed algorithms in weal-world settings would provide valuable evidence of its practical applicability. In particular, such experiments could help assess two modeling choices: the adequacy of modeling the expected product conversion rate using linear functions, and the robustness of focusing only on very recent ad exposures due to recency bias. However, given the lack of publicly available online advertising and bidding datasets, we leave this empirical validation to future work as important step toward bridging the gap between theory and practice.
10

---

References
ITA.
E-commerce Sales Size and Forecast, 2025.
URL https: htwp//wwwwwoo trade gov/
<comerre-saalesssiee--ooraa Accessed: 2025-01-25.
Gagan Aggarwal, Ashwinkumar Badanidiyuru. Santiago R Balseiro, Kshipra Bhawalkar, Yuan Deng.
Zhe Feng, Gagan Goel, Christopher Liaw, Haihao Lu, Mohammad Mahdian, et al. Auto-bidding and auctions in online advertising: A survey. ACM SIGecom Exchanges, 22(1):159-183, 2024.
Google Ads Support. About Automated Bidding in Google Ads, 2025. URL google booogle.co/ggoe google-ogllooooooo http////ee//9///111///
Accessed: 2025-01-25,
Facebook Ads. About Automattd Bidding on Facebook Ads, 2025. URL https://wwi lttp::://wwwffaceboo
Accessed: 2025-01-25.
Microsoft Ads. Automated Bidding Tools for Performance Optimization, 2025.
URL https: Accessed:
//about.. ads microsoft. wtt.p/ott......oaoooo//ooraoaaan
2025-01-25.
Amazon Ads. Dynamic Bidding for Sponsored Products Guide, 2025. URL.https://dvveriiisit Accessed: 2025-
amazon.
01-25.
Demetrios Vakratsas and Tim Ambler. How advertising works: what do we really know? Journal of marketing, 63(1):26-43, 1999.
Randall Lewis and Jeffrey Wong. Incrementality bidding and attribution, 2022. URL https
7/arxiv. abs abs/aaas//a 2208. 12809
Virgilijus Sakalauskas and Dalia Kriksciuniene. Personalized advertising in e-commerce: Using clickstream data to target high-value customers. Algorithms, 17(1):27, 2024.
Hao Liu, Yunze Li, Qinyu Cao, Guang Qiu, and Jiming Chen. Estimating individual advertising effect in e-commerce. arXiv preprint arXiv: 0tt:::9900.44411 2019.
Brett Gordon, Florian Zettelmeyer, Neha Bhargava, and Dan Chapsky. comparison of approaches to advertising measurement; Evidence from big field experiments at facebook. Marketing Science, 38(2):193-2255 2019.
Cornelia Pechmann and David W Stewart. Advertising repetition: A critical review of wearin and wearout. Current issues and research in advertising. 11(1-2):285-322 1988.
Vicki Lane. The impact of ad repetition and ad content on consumer perceptions of incongruent extensions. Journal of Marketing, 64(2):80-91, 2000.
Socun You, Tacha Kim, and Hoon S Cha. The smartphone user's dilemma among personaliza- tion, privacy, and advertisement fatigue: An empirical examination personalized smartphone advertisement. Information Systems Review, 17(2):77-100, 2015.
Raoul Bell, Laura Mieth, and Axel Buchner. Coping with high advertising exposure: source-
monitoring perspective. Cognitive Research: Principles and Implications, 7(1):82, 2022.
Rui Guo and Zhengrui Jiang. Optimal dynamic advertising policy considering consumer ad fatigue. Decision Support Systems, 187:1 14323, 2024.
Jonathan Weed, Vianney Perchet, and Philippe Rigollet. Online learning in repeated auctions.
In Vitaly Feldman, Alexander Rakhlin, and Ohad Shamir, editors, 29th Annual Conference on Learning Theory, volume 49 of Proceedings of Machine Learning Research, pages 1562-1583, Columbia University, New York, New York, USA, 23-26 Jun 2016. PMLR. URL https:/7
proceedings mlr htw.:///ng..i.....e////////// wwtps///e/eeeeeeee.eeeeee html
Evert De Haan, Thorsten Wiesel, and Koen Pauwels. The effectiveness of different forms of online advertising for purchase conversion multiple-channel attribution framework. International journal of research in marketing, 4915577 2016.

---

Kan Ren, Weinan Zhang, Ke Chang. Yifei Rong, Yong Yu, and Jun Wang. Bidding machine: Learning to bid for directly optimizing profits display advertising. IEEE Transactions on Knowledge and Data Engineering, 30(4):645-65) 659, 2017.
Zhe Feng, Chara Podimata, and Vasilis Syrgkanis. Learning to bid without knowing your value. In Proceedings of the 2018 ACM Conference on Economics and Computation, pages 505-522, 2018.
Zhe Feng, Christopher Liaw, and Zixin Zhou. Improved online learning algorithms for ctr prediction in ad auctions. In International Conference on Machine Learning, pages 9921-9937. PMLR, 2023,
Yanjun Han, Tsachy Weissman, and Zhengyuan Zhou. Optimal no-regret learning in repeated
first-price auctions. Operations Research, 2024.
Mengxiao Zhang and Haipeng Luo. Online learning in contextual second-price pay-per-click auctions. In International Conference on Artificial Intelligence and Statistics, pages 2395-2403 PMLR, 2024.
Yuan Deng, Negin Golrezaei. Patrick Jaillet, Jason Cheuk Nam Liang, and Vahab Mirrokni. Fairness in the autobidding world with machine-leamed advice. arXiv preprint arXiv:2209.04748, 4, 2022.
Tengyun Wang, Haizhi Yang, Han Yu, Wenjun Zhou, Yang Liu, and Hengjic Song. A revenue- maximizing bidding strategy for demand-side platforms. IEEE Access, 7:68692-68706, 2019.
Ashwinkumar Badanidiyura, Zhe Feng, Tianxi Li, and Haifeng Xu. Incrementality bidding via reinforcement learning under mixed and delayed rewards, 2023. URL https://arxivv.rrr
Assaf Hallak, Dotan Di Castro, and Shie Mannor. Contextual markov decision processes. arXiv preprint arXiv:1502.0223: 2015.
Orin Levy and Yishay Mansour. Optimism in face of a context:regret guarantees for stochastic contextual mdp. Proceedings of the AAAI Conference Artificial Intelligence, 37(7):8510-851 2023. doi: 10. (009//ai.v3377.... 26025.. URL https://ojs aaai. org/ orggoiogesss iindxxidxxx//// php/AAAI
article/view/2602
Binita Manandhar. Effect of advertisement in consumer behavior. Management Dynamics, 21(1): 46-54, 2018
Jamie Murphy, Charles Hofacker, and Richard Mizerski. Primacy and recency effects clicking behavior. Journal of conputer-mediated communication, 11(2):52-5335, 2006.
T Chatfield. The trouble with big data? it's called the 'recency bias'. BBC. Retrieved April, 28:2023, 2016.
Gloria Phillips-Wres Daniel Power, and Manuel Mora. Cognitive bias, decision styles, and risk attitudes in decision making and dss, 2019.
Google Ads Attribution. Guide To Google Ads Attribution Models in 2025 Is Data- Driven Attribution The Future?, 2025. URL sttpp:://au..dttaffeewwaaa dawafaedwattccchhcceecmmaaaa Accessed: 2025-05-11.
com/blog/
google www.add--attrrbbitooooooeeeeeeee
Nicolo
Claudio Gentile, and Yishay Mansour. Regret minimization for reserve prices in second-pric auctions. IEEE Transactions on Information Theory, (1(1):449 2014.
Wei Zhang, Yanjun Han, Zhengyuan Zhou, Aaron Flores, and Tsachy Weissman. Leveraging the hints: Adaptive bidding in repeated first-price auctions. Advances in Neural Information Processing Systems, 35:21329-213411. 2022.
Google Developers. Authorized buyers real-time bidding (rtb) protocol guide, 2024. URL https //developers. oo/tooecco/mttttoriiieeeeeeeeeee wttprriiiiiiiiiieeeeerrr/r//eeae guide Accessed: 2024-
01-30.
Jean-Jacques Laffont, Herve Ossard, and Quang Vuong. Econometrics of first-price auctions. Econometrica: Journal of the Econometric Society, pages 953-980, 1995.
12

---

feedback under the Robert Wilson. Sequential equilibria of asymmetric ascending auctions: The case of log- normal distributions. Economic Theory, 12:433 4400, 1998.
Eric Smith, Doyne Farmer, László Gillemot, and Supriya Krishnamurthy. Statistical theory of the continuous double auction. Quantitative finance, 3(6):481, 2003.
Martin Skitmore. First and second price independent values sealed bid procurement auctions: some
scalar equilibrium results. Construction Management and Economics, 26(8):787-803, 2008
Pablo Ballesteros- Pérez and Martin Skitmore. On the distribution of bids for construction contract auctions. Construction Management and Economics, 35(3):106-121. 2017.
David J Cooper and Hanming Fang. Understanding overbidding in second price auctions: An experimental study. The Economic Journal, 1 186532) 2008.
Haoyu Zhao and Wei Chen. Online second price auction with con-stationary setting. arXiv preprint arXiv:1911.05944 2019.
Yasin Abbasi-Yadkori, Dávid Pál, and Csaba Szepesvári. Improved algorithms for linear stochastic bandits. Advances in neural information processing systems. 24, 2011.
Bo Xue, Yimu Wang, Yuanyu Wan, Jinfeng Yi, and Lijun Zhang, Efficient algorithms for generalized linear bandits with heavy-tailed rewards. Advances in Neural Information Processing Systems, 36, 2024.
Radhakrishna Rao. Information and the accuracy attainable in the estimation of statistical param- eters. In Breakthroughs in Statistics: Foundations and basic theory, pages 235-247. Springer, 1992.
Aditya Modi and Ambuj Tewari. No-regret exploration in contextual reinforcement learning. In Conference on Uncertainty Artificial Intelligence, pages 829-838. PMLR, 2020.
Orin Levy and Yishay Mansour. Learning efficiently function approximation for contextual mdp, 2022. URL /tttp:://///xx org/ abs 2203. 00995
Orin Levy, Alon Cohen, Asaf Cassel, and Yishay Mansour. Efficient rate optimal regret for adversarial contextual MDPs using online function approximation. Andreas Krause, Emma Brunskill, Kyunghyun Cho, Barbara Engelhardt, Sivan Sabato, and Jonathan Scarlett, editors, Proceedings of the 40th International Conference on Machine Learning, volume 202 of Proceedings of Machine Learning Research, pages 19287-19314, PMLR, 23-29 Jul 2023. httpst httttp:://rrceedings
mlr. www.prree/v22/2eev22232 html
Michael Kearns and Satinder Singh. Near-optimal reinforcement learning in polynomial time.
Machine learning, 49:209-232, 2002.
Ashwinkumar Badanidiyuru, Zhe Feng, and Guru Guruganesh. Learning to bid in contextual first price auctions, 2021.
Yiling Jia, Weitong Zhang, Dongruo Zhou, Quanquan Gu, and Hongning Wang. Learning neural contextual bandits through perturbed rewards. arXiv preprint arXiv:2201.099) 20990990,, 2022.
Chi Jin, Zhuoran Yang, Zhaoran Wang, and Michael Jordan. Provably efficient reinforcement learning with linear function approximation. In Conference on learning theory, pages 2137-2143. PMLR, 2020.
Jiafan He, Dongruo Zhou, Tong Zhang, and Quanquan Gu. Nearly optimal algorithms for linear contextual bandits with adversarial corruptions. Advances in neural information processing systems, 35:34614-34625, 2022.
Alekh Agarwal, Nan Jiang, Sham M Kakade, and Wen Sun. Reinforcement learning: Theory and algorithms. CS Dept., UW Seattle, Seattle, WA, USA, Tech. Rep, 32:96, 2019.
Martin J Wainwright. Hiigh-dimensional statistics: A non-asymptotic viewpoint, volume 48, Cam- bridge university press, 2019.
Botao Hao, Tor Lattimore, Csaba Szepesvári, and Mengdi Wang. Online sparse reinforcement
learning. In International Conference on Artificial Intelligence and Statistics, pages 316-324. PMLR, 2021.
13

---

Appendix to "Learning Personalized Ad Impact via Contextual Reinforcement Learning under Delayed Rewards"
A Additional Discussion
A.1 Related Work
Motivated by online advertising auctions, Weed et al. (0166] study repeated Vickrey auctions where goods with unknown values (1x) are sold sequentially. Bidders receive (potentially noisy) feedback about good's value only after purchasing it it-analogous to observing product conversions after displaying an ad. They formulate this problem online learning with bandit feedback and propose danimax-optimma bidding strategy for bidding (b.). However, a key limitation of their model the neglect of long-term advertising effects: winning bid at time t may influence future observations and outcomes, such as conversions at time + 1. Building on this line of work, Feng et al. (018]] examines learning bid without knowing one's value in similar bandit setting and develops the WIN-EXP algorithm, which achieves sublinear regret (O(VT)C log( B))). Yet, like the earlier study, it assumes that the effect of winning a bid is instantaneous, ignoring possible intertemporal dependencies.
In a related direction, Han et al. [2024] investigate online learning in repeated first-price auctions, where bidder observes only the winning bid after each auction and must adaptively learn to winning bidders cannot observe their competitors' bids-they design the first algorithm achieving near-optimal (O( ((T))) regret by exploiting structural properties of first-price auctions, including their feedback and payoff functions. They formulate the problem as partially ordered contextual bandits, incorporating graph feedback across actions, cross -ross-leanning across contexts, and partial order over private values. Nonetheless, their framework similarly assumes independence between the value process (w)) and past bidding outcomes, thereby excluding long-term effects of winning bids.
maximize cumulative payoff. Facing censored feedback-
Extending to contextual settings, ZZhang and Luo (2024) study online learning in contextual pay- per-elick auctions. At each of I" rounds, the learner observes contextual information and set of candidate ads, estimates their click-through rates (CTRs), and conducts a second-price pay-per-click auction. The objective is to minimize regret relative an oracle that makes perfect CTR predictions. They show that VT-regret rate is achievable (albeit with computational inefficiency) and provably optimal, as the problem reduces to the classical multi-armed bandit setting.
While these studies advance our understanding of strategic bidding under uncertainty, they share common limitation: none account for the reinforcement or long-terry impact of successful ad displays. This omission contrasts with empirical evidence such as De Haan et al. (2016), who demonstrate that online advertisements exert persistent effects on purchase conversion in multi-channel attribution Wranwork-thouuge their dataset is not publicly available.
More recently, [Badanidiyuru al. 202T address this gap by modeling the long-term causal impact of ad impressions using a Markov Decision Process (MDP) with mixed and delayed Poisson rewards. However, their approach assumes homogeneous treatment effects across users, overlooking the crucial role of personalization in determining ad advertising effectiveness. To address these limitations, our work jointly models the long-term, reinforcing, and personalized effects of advertisements, hoping to bridge the gap between sequential decision-maid makinng and individualized ad impact estimation.
A.2 On the Potential to Extend the Linearity Assumption
Briefly recap of our model (Assumption 2.2). if we won the bid of, 1, the average product conversion rate H² heg (xx), where x; is the received feature of customer, and S the state which captures the time elapsed since most recent ads impression, hs;, the state dependent neural network which we want estimate. If we lose the bid of, the average product conversion rate 1 dst,, hts,,, (Xe), where ds;, is the delayed impact, and 5% is the time interval between the two most recent impressions (Def
14

---

To incorporate the estimation of the state-dependent neural network hy (analogous to 8₁) into our algorithm, we could do follows. Everything Algorithm Iremains unchanged, i.e. the exploration. exploitation, data- hata-splitting strategy, and estimation, exception the following modifications.
First, we replace the estimation 0, (Eqn. (4)) by estimating the neural network by by the following procedure (similar to Algorithm in Jia al. (2022)).
We approximate h(xx) by f(x, 0) = (oWeWooWWLeeee the neural network depth.
((W1x))) where m is the
network width, and ((x) ReLU (x),
We initialize Og = (vec(Wi).... ... ver(Wr)) by random sample entry from (0, 4/m) and do online updating by gradient descent with perturbed reward using observed product conversion vi, by follows
* Generated observation perturbation Y.e10 ~ Poi(A), then generate binomial ran- dom variable [c([]]
to add or subtract the noise from the observation
min L(0) -(F(x, - (y + / mm 0/ll2/2
Then based on this first stage estimates of h. plugging in estimate delayed impact E.st EnED,, yi
factor d by E: Ei /sz,p (x (analogous to Eqn.
Since we do not have theoretical guarantees for h estimation (no confidence interval), we cannot do upper confidence bound (Line 10 of our Algorithm [ Instead, we might act greedily based on our point estimate. Even though Algorithm in Dia et al. [0222] has theoretical guarantees, the key difference that they assume noise of their observation is sub-Gaussian, while in our case, it is not realistic to assume that the observation y has sub- Gaussiassii noise, since product conversion has been known to have heavy tail for a long period of time. It is still challenging open problem of developing neural contextual bandits with heavy tail observations.
pereetical-uurannter
However, our proposed framework leads to near-optimal results if we can parameterize lx,).) O, o(x:), where o can be the neural net based embedding other known feature mapping, then our algorithm remains near optimal, satisfying vT regret bound in this case. This construction is very common in academia and industry as we mentioned from foundational studies such as Jin et al. [2020) to the recent ones [He et al., [022]. In addition, in real world, companies might construct these feature mapping using complicated methods but retain the overall linear structure for the case of scalability and interpretability. For example, the expected conversion rate could be a linear function of the expected webpage stay time and the predicted total spending but the expected webpage stay time and the predicted total spending are deep neural networks of the observed customer feature x,-
To summarize, our proposed framework leads to near-optimal results if there exists an online estimation oracle with theoretical guarantee for the estimation of and the estimation oracle employed in our paper based on our knowledge is state-of-the-art Our algorithm is possible to extend to a neural network if drop the theoretical concerns. Developing theoretical guarantee for neural bandits under heavy tail observation could be promising future direction.
A.3 Flexibility in State Space Modeling
If we believe that all past ad exposures contribute to customer behavior, can enrich the state variable to S = [S% S 2. ne,1, where ni, denotes the total number of ads the user has seen prior to round h. Under this formulation, the expected conversion from showing an ad at round h is given by [0st,.n .f. xt), with other modeling assumptions unchanged. In other words, the effect of the current ad depends not only on the time since the last impression, h - G (as shown in Figure T. but also on the cumulative number of ad exposures the user has experienced so far.
Accordingly, Assumption 2.2 as follows:
1. When of = O, no ad is shown at round h, and the effect of recent ads at G%, carries over, given by (0 2m0) -1vo: Xx) ds; where V denotes max(a. (a, b).
15

---

2. When of 1. an ad is shown at round h, and the impact of the current ad is modeled as (0 sy m X,), influenced by all the past ads exposure history.
We emphasize that, two-stage estimator, and the iilorattoo-exploitatiio algorithm, readily extends to this new model with the enriched state representation. In addition, theoretical results continue to hold under this new model, with a new optimal regret bound of order O(HH VT). in comparison OdH2 VT) under the previous model. We provide supporting evidence below.
algorithmic design, including the data-splitting strategy, the proposed
Now the enriched states is S [S S4.1
In terms of state transition, if of, = 11 -,,5
[1. 1 n + 1]; else, + = [S S1.5 n/]. now becomes M.ne U ( with H {11, n) : H4 UH2 < I]. H1 foo, 1,2..... H - 1} and H2 {-00, 1, H 2}.
For data spiting strategy in Def 3.1 D does not change and W will extend to W = {4|5% = 1, nf o 1}, vi [20, 1, ...., H). Wt. W. {h|Sh -00, n n1 of, = 0}. Also, wi will extend Wi.,. [W (Wa,.d The estimation of 01,1 using observation in Wi, still follows online newton estimator with Eqn. 4 The TS-MLE now becomes
E. EneD., Va
dj
E.T1 EXED,, (0 2 Ivo X.)
Plugging in these new estimators in to the regret decomposition (Eqn. (9) Term (i) and Term (iv) does change since new states did not affect transition error. For the estimation error, Term (iii), we just need an additional for loop to account the effect of n/,,, which makes the new regret upper bound now O(dH)VT).
The above example suggests that our state formulation is very flexible and readily accommodates an enlarged state space. It supports a broad class of CMDP formulations for Os, where S encodes domain knowledge about ad effects, and remains compatible with our proposed learning algorithm.
A.4 Illustrative Example
win, -o =1
win, of =1
/
=
yi
y2
y yt y
Figure Illustration of Learner-Custome Interaction CMDP
Figure 2 presents a simple example of a customer, with contextual x, and no prior ad exposure, interacting with the learner over H rounds. At the start of each round, L observes the state S determines the bid amount ai, = ne (S, xx) based on policy ne, observes HOB mi,, and receives the bidding outcome of, along with the reward Rt (St. . a/. xx). At the end of each round, L observes the total product conversion yi over the current round. As shown in Figure 2 the customer's ' first ad impression occurs at h resulting in S St S [-o0, so] and li μ/= (0.... xi) (4j defined in 2.f The first ads exposure updates the expected conversion to μá = (0 Xt). capturing the immedhate impact of ad exposure. The second ad impression occurs at 6. Between h = and h = 6, the state evolves as S [1, oo), Sgg [2. o conversions µ di (0x,, x,) and μ = (0xx, x.). reflecting the delayed and long-term impact of the ad displayed at h = 3. p = (O2 xt), capturing the effect of repeated ad exposure. Finally, = 7, S4 = [1,3] and 14 = (0,, x,), demonstrating the long-term effects of the second ad impression.
co), with expected
16

---

A.5 Computational Complexity
For each episode of Algorithm the computational complexities for updating 0; 3/ and di are O(d)) [Xue et al. 2024 (ld)), and Old), respectively, for each E H. Notably, for fixed policy æ and transition _=x, R(T, O FFa) is nondecreasing in di and 0,, simpli- ) The corresponding maximizer are dj d B. d. (1g ht (2) and 0 0 x [vp)
fying the computation of max R(:;
VTVV) x, obttained via constrained
by
linear optimization, where 0f is from Eqn. and fy is from Lemma
3.3
The greedy policy π is then
computed via dynamie programming with time complexity Poly( H, [8] Ba/c) when discretizing the bidding space for an c-optimal solution (Agarwal et al. 2019
Details of Omitted Algorithm
In this section, we detail the algorithm used to estimate 0 for E H. Originally introduced by Xue et al. [2024), the Confidence Region with Truncated Mean (CRTM) algorithm (Algorithm 3) serves as an efficient estimator for generalized bandits with heavy-tailed rewards. their framework, the stochastic observations y; follow generalized lincar model:
yix, 0 - -m(x,00 01) M(x).))
P(y)|x)) = exp
g(T)
where 0 represents the inherent parameters, 0 is known scale parameter, and g(-) and h(-) are normalizers. The conditional expectation of y: given by:
E(y,|x,) m' (x, 0:),
where m m²(-) is the link function, denoted as y(-) m'(+). Thus, yr can be expressed as:
y, pxx, 01) + ne=
where Tt is random noise term satisfying E(n( (x1.Y1..... Y1-1, denotes the o-filtration up to time 1. CRTM assumes that the link function u(.) is L-Lipschitz, continuously differentiable, and has a first derivative μ (-)- bounded below by a positive constant K, i.e., pz) 2 к. Additionally, CRTM assumes that the observations y, have bounded moments. Specifically, there exist positive constants and 0 S 1 such that:
0. Here, G--1
Ete Gr-1) u.
In our setting, where y, follows Poisson distribution, we have e = 1, B, + B, Bo), n())) as linear function, and 1. Based on the specific parameters our setting, the CRTM algorithm (Algorithm 3 is adapted as follows:
17

---

Algorithm 3 Confidence Region with Truncated Mean
[ue et al.
2024
Require: Wt., Xt, V 1 7
1: for yi W,, do
2: Truncate the observed payoff: y -ii-lixxll - II
3: Compute the gradient: vi,(0--) (-9 + x, 0j ')x
4: Update V V Xx
5: Update the estimator:
0 0
11
0 arg min BER
(0 vi.(0-1)
6: Construct the confidence region:
C = { 0: E IRd 1 011i; $7
7: end for
8:
refurn ()
In particular, the truncation threshold I' is defined by Equ.
10
47
7
r = 2 B. B. B, log
d dlogg
1
(10)
8
2d
Moreover, the bound for the weighted estimation error, ||0: 2 denoted by 7, is given by:
4T
T 2d
T
7 = 896dB, + Ba) log
log
+ +2BB 48dB log
2d
Running Algorithm leads to the following lemma.
Lemma (Lemma 3.3 restated). Given / E H. with probability at least 1 - 6, 0 defined in Eqn. satisfies ||0 0 ON S 7, 7, 0.
C Proof of Theorem 4.2
Theorem (Theorem 4.2 restated). For any 8 2 73. with probability least Regy incurred by
Algorithm is OdH2 Togg TH log(1 + 22 ))
T
Proof. In this section, we present the detailed proof of Theorem 4.2 We begin by decomposing Reg, (defined in Eqn. ( into four terms-Ter (i), Term (ii), Term (ii), and Term (iv)-as shown
18

---

in Eqn. 9 (log T) comes from regret incurred in the exploration phase with T = Hn + 1.
Reg,
OPT (O, Fx.) E Ta.. F
Σ
R X,,
OPT (0, x1, frc. (t,1)
<O T) + OPT (0,
x,,
Term (i)
T
Σ OPT O 0x:1
Σ OPT (G--1, XX, xt, +
Term (i8)
T
T
Σ OPT Xe, - ErI BE
Σ
R TTi ,, Frc
Term (11)
T [TT X1, O,Fa1) O, Σ
Em Bm R
Σ R
Te: 0
E Sp Spp
Term (iv)
At a high level, Terms (i) and (iv) account for the cumulative regret from transition error, i.e., the discrepancy between FX: and Fx: Term (iii) represents the decision error arising from imprecise estimates of the model parameters = {0i) U [ell) Thus, more accurate estimators of JTx and @ yield lower cumulative regret. Mcanwhile, Term (ii) measures the gap in regret between chosen point and the optimal point within a feasible set. Our goal is to show @ C. for 2 T (after the exploration phase) with high probability, ensuring that Term (ii) can be negative with high probability. This is proved in Lemma 4.5 By Lemma 4.3 with probability at least 74, Term (i) in Eqn. (9) is bounded by (d)) A similar argument implies that Term (iv) is also bounded by (ddI2vTT with probability at least T Further, Lemma 4.4 shows that, with probability at least 1 S.. Term (iii) is bounded by O(H2VdT) Combining these results, we conclude that, with probability at least 1 - 7s. the overall regret Regr is (dHHVV).
C.1 Proof for Theorem 4.1
Theorem (Theorem
4.1 restated). Let 2 ThE and No,1 2 ny. With probability at least 5, the estimation error d di) with di defined Eqn. (3) is bounded by:
d/ AHBay d logg(1 T) Be Bg log !
|
b Ne.
Y is as defined in Lemma
3.3 and nı defined in Remark 3.2
The key idea in estimating d; is to isolate observations that are "purified" with respect to d- Define
Proof.
D {h Sh = 0 =0}
which collects the episodes for user where: The second-to-lass bid winning is / episodes before the most recent bid winning (S), I); The current bid is lost (o), 0), meaning new advertisement shown. Under these conditions, the product-conversion observations (yf)eeD satisfy
y ~ Poi (0s (oi(dd(ss;, xx))-
Because these observations are purified within the same I that defines d,, they provide reliable information for estimating the long-term advertising impact parameter dr. To estimate the long-term advertising impact parameter d,, we adopt two-stage procedure. First, we construct the estimates
19

---

0 for all E [t]. Then, we substitute these estimates into the negative log- oog-likelhhod for di (see yielding our two-stage estimator for di.
Eqn.
11
fly: 0)
Σ
Σ
d1 51,2" Xx) yi, log (di(0s xsi)
(11)
#=1 h.D
Taking the derivative of the negative oog-lieelhhood with respect di yields:
Va,((y;)) Σ bED..!
(0s
xx)
y
(12)
di
This expression guides the next step of solving for dj. By solving Eqn. di for di as follows:
12
we obtain the estimator
E. EIED., Y
df
Σ EnED.,, (0s Xx)
Here, $ denotes the updated estimate of the advertisement's 's impact for user s. Next, we bound
the estimation error of di. We express y as
yi = d x Os + v/:
where Vij is sub-exponential with parameters (12,a) = (ed x. 0s 1) (see Lemma D.1
Based
on this formulation, the estimation error d, dil can be decomposed follows.
El= EnED,, yh
ldj- dil
dl
E.= ENED..
(0 2/222 (x,)
E1=1 EnED...
[ix, 05h.2 Thh
di
Ei=1 ELED,,
(0 51,2"
Xx)
E'=1 ΣnED,, Thi
di Ei= ΣnED.. x? (0s%, 03 di
+d
Σ EneD,, 2/22" Xx)
E' ELED,, (03 xx)
Σ Σ ENED,, Xx)
s=1 ELED, T
Σl ENED,, 1 x 0s 0 03g.0
+ dl
Ei EnED,, 10s xs)
smm ΣLED,, T
Ba
Σ x 0s 055
Σ ΣnED,, ( 2/22" x,)
N
RED...
Torm ()
Term (ii)
(13)
To upper bound the estimation enror (see Eqn. respectively. We can use sub-exponential concentration bound for Term (i), shown follows.
1 ). it suffices to bound Term (i) and Term (ii) in Equ.
E ENED,, n Σ ΣLED,, (0st. Xx)
Σ EMED..
n
m. SubE (edix, OsT.
P
>
S
Nr
No.1
1
P
>
X, SubE(cB.B..o.
b
N₂,1
< 8.
(14)
20

---

We derive Eqn. (14) by applying the tail bounds for sub-exponential random variables (Lemmas D.4 and D.6 and setting
D.5
2e Ba Be
log(
E e=1
b² N1,
We also use the accelerated convergence rate for sub-exponential variables under the conditions S c I Ba B Bg. Therefore, with probability at least 8, have Term (i) 2e Ba B. Be log, ()) Then it remains to bound Term
Ni. > log(HT) and 5 2 2HT which ensure
Ba B, Ba
N..1
(ii) in Eqn. Define the dataset F!. 2,l' = {h} 5h = S7 1", of = 0}. Observe that
Σ
F
[Da.l:
meaning Fyyy partitions Da,, according to Sh the second-to-last winning state. Let na, := FFayl Then
H
na.
N1,1-
am
1==1
Since |001122 I BB for all I, and
|xx122 I Be for each s [T]. define
r
(0 $2.2
0s X
||0% 0gg llv, |xx|l((;;--
where l' = 2
For convenience, let VT
1 3
0 Ss llv Then, with probability at least
1 - 8, we have
Σ
(0
05
X,
rh
RED..!
heD
/N
Σ Σ
(r2)2
hED..!
-VNr
Σ
(rg)²
1'=l''ehh lhee!
-VNu
ns min (1xxll(v3)1111))
-VNua
nu min (Ixollez3) 2,1)
(15)
SVNui
nay min (1xxIl(13)~1111
SVNiiH
min (1x0Il(v33-1111
SH <H No
7 max Me (
Σ min (1xxll(vp)-1;11
T [+
<2HVd No,
7.
2d
21

---

Therefore, with probability at least 1 - -5,82 H74,
_1
we have
AH dlog (1+ 2 V2e Bo log(2/5)
1
ld del s
b
VNul
C.2 Proof of Lemma 4.3
Lemma (Lemma 4.3 restated). For ò 2 1/T", with probability at least - 6, Term (i) in Eqn. 9 is bounded above by
T/dd)
Proof. essence, the proof Lemma relies on two main steps. First, we show that Term (i) can be bounded by the cumulative estimation error in transition, expressed as
Σ supsup (b, x:) (b, x.)
Second, we demonstrate that, when (b, x²) is estimated using Algorithm this cumulative estimation error remains small. Combined, these two steps yield the desired upper bound on Term (i).
Step 1: Upper bound Term (i) by the cumulative estimation error in transition.
Term (i) captures the regret induced by transition error, as shown in Eqn. (T6). The final inequality
in Eqn. TT)p holds because H(T); (a)) OPT(O, Xx, Fr <
0, due to the definition of
OPT θ xx. F2.) We then apply the Simulation Lemma (Lemma C.1 to bound R(T;; 0,
R(T]: ; 9, PM.))
x,, Fkc) - Σ OPT (0, X1, (t, Σ OPT (1,
Term (i)
T
0,
R(T;: , (r R OPT (o.x (16)
$
Σ
t=r
Lemma C.1 (Simulation Lemma
Kearns and Singh 2002 ). For all E S and a E A, if
Eves P(s' s)) - (P'(s' s, a)
I e1 and vh E [H], (s) - (s)) S 62 then
H(H 1)61
E Rysnan 1M ~
Σ kE(H)
an 3M ~M'
Σ kE[M]
H c2
To find ej in Lemma
we compare two MDPs:
M,, induced by policy Tū, 0, and HOB distribution Fx:
and
Mr. induced by policy क 0, and HOB distribution F
Given state 82), have:
Σ
Pa(s'(s, Pa a)
|P = (81 + 1,82))8, a) Pn(s' = (81 + 1882))8,
S'ES
+ Ph(s' = =(1, a) - Pm = (1)(s,)))))
(17)
= 2 -
(1) - Fn(ax
< supsuup
F (b, x1) - (b.
b h
22

---

Define
Frh (b, x,) - (b(b,x,))
4 = sup sup
From Eqn. 17 it follows that the parameter 6j in Lemma C.I can be taken as 24g. the following, we
bound the difference between Rt, and Rt find 62 in Lemma C.I By definition, Rtj (5% Af, x,)
dst,, (0st. -1- xx) ((0st.. xx) Ph (A X J (A xx). Here, Ph (A xx) is the
second highest price conditioned on winning, Since ph: (b) = b Jnbbi So Fn(u, xx) de, we obtain
Pa (A X²) - (Af. xx) - (A x4) = So² Fn xt) do - S F (u, xt) de.
In addition, we can show
10 [(o)do - -f" f(o)du 1." sup [B())(()))))))))))()))))) - f(
sup (fp))(x) f(())] / 1dv
(f f(xx)).
Therefore, we can bound the reward difference [R Ry (s. a)l by Eqn. (18)
R/
(gtt (0s x1) + (Ost., x1) + BA)
j - (b,x,) Fb,
sup BAl h
sup
- ((Ba + 1) + BA) sup BA] h
sup
jt Ht- (b,x,) x1) Fb(b,x))
= 11 + BA)E..
(18)
Combining Eqn. 17 and Eqn.
18
Lemma
C.1
implies
[[m];, R(TT f S H(I - 1)e, H(BB, 1)B, + BA)e:
=
H&e, + H + 1)B, - -BA - 1)4.
(19)
Therefore, by Eqn.
19 bounding Term (i) reduces to bounding
T Σ
H (B( Bo + BA 1)a).
Step Construct high probability bound for cumulative estimation error transition The next step is to derive a brobabioyyyylity bound for Σt=r et. By Assumption 2.6 the Highest Other Bids (HOB) distribution satisfies log(m({) ~ N(xx,, Br), af), suggesting that the transition estimation error takes the form
F (b, - Fabb, x:) ④ (log(b)
(x,, 3/-1) - (log(b) 1hx,,3n)) _--1
(20)
ah
Using a first-order Taylor expansion of the standard normal CDF (f-), we obtain (a(a) + (a A s A [o((), o is the standard normal pdf. This inequality allows us to further bound the
(xx 1111) where |A) is defined
estimation error by (b, Fn xx) < |
23

---

and bounded by follows.
log(b) (xt,
1x,,,/11 3/
log(b) - (xc, Bn))
h
Th
log(b)
(xt, 3/- log(t) - (xx,, 1/-1))
log(b) (xx, 3/
log(b) (x,, Brr)
g-11
Th
Th
Th
1
T
(8h-1 -Ba) + log(b) - -xx1..%% 1/
1
x
61-1 Th
4h
1
T
(8%-1
Bh)) (log( BA) + BB)
Oh + +.
(0
x
hh
(nn
(21)
Note that we estimate the variance of using second-stage empirical estimates. Concretely,
(lg(mm;)) x3 -x, (3)3 2
(6)
Meanwhile, by definition,
o - Σ [og(m)) - x,_ B1 Bn]
To complete the argument, it suffices to show that these two quantities are close with high probability.
oh (0/-1)
log(m;)) - x3 (.. E (log(m;) x3 B,))
(log(m²) - x3 + xx -x, (i) (log(m))) x3 Bn)²
(log(m²) x_ Bn)² (log(m²) x3 (,))
x Br - -x, 33: 2
+2
(log(mn,)) - B1) (x] Br. - x3 3%)
Using Eqns.
20
21 and (6) derive the following equations:
T
T
Σ
x, BB) 3n)
4
sup
t= helf Th
Term A
1
+2 (log( BB 2
sup Ch hEH
x
33 B%h
Term
x Br xx_ xT1²%) 2
+ (log BA) + B,
sup kelf
Term
+ +logg( BA) + B B₁)
(log(mā) - x, Bn)² (log(mī) - x3 Bn)²
Term D
(22)
24

---

where C₂ oh-
(aNd) I qe. by Assumption 2.8 In what follows, we bound each term one by one.
To bound Term A, we show that for all h, with probability at least the following holds:
T
T
x2
(3%
x
[ - Bn.)
t=1
T
min
2BBB.s ||X||| (x))) (x)
1115%
Bullsg
==1
2B3B,
Bulls 5:
min
1|1x
h
11,3%=
(D%
1 + TB2/1
T
1 dlog
VABB
T
min
1, [1,1|el] (2) 1-11 by Lemma D.2
1 TBB42/1
TB2
1
dlog
VAB3
Tdlog
1+
Ad
< dvT sup WEH
2 oh
log
1 +BBB
+ +VAB8)
/
log
1+
TB₁
8
Ad
Therefore,
TB²
TB, Ad
Σ sup x - 3n)l S d dvT bell Th
V
log
vABB) V log
This shows that Term on the order of (loo T). For Term B, similar argument implies that, with probability at least - 8,
d
62
TB² + vABa) log 1
(3 BBh)
log
TB
Ad
vt
a
Therefore, we conclude the following bound.
Σ sup Ch
T
1-1 x B (3%-11) 3%)
< dvT
20 g
log
1 TBB/
+ vXBB / |ogg
11
TB, Ad
t hell
8
remains bound Term First, observe that
(log(m))
x3 Ba) -1)
[[og((m))) -x, x3 Bn)² 10---EEaa (loo(mm)) xx_ Bn) =o
oî (xi-1)
o
Since Xi SubE(4, 4), by Lemma C.2 and union bound argument, we can show that, with probability at least 1 - ô, Term D is bounded above by
21 log
VT
(log(T)).
The O (I))(TT)) term arises from "burning in" the first 64 log(T) which guarantees 8 2 1/4T* and ensure quadratic decay of sub-exponential bound.
Lemma C.2 (Example 2.11 in Wainwright (2019). A chi-squared (x2) random variable with degrees freedom, denoted by Y X", can represented Y -Ek Zg, where Z N 1) are i...d. variables. Since each Z sub-exponential with parameters (V² (v2.a) (2, 4), we have
( E z 1 2 V log 2) S 6, as long as ė 2 exp(-=))
25

---

Bringing all these results together and applying union bound, we conclude that there exists constant C. depending on B, Bp, B3, 0, 0, Ba, and A. such that with probability at least 1 (where
8 2 TT). ) we have
1 1
T Xd
Term (1) S Cd VT
log
log 1
Ad
By choosing A 1, we proves Lemma 4.3
we states that for 5 2 1/T1, with probability at least
1 - 6, Term (i) in Eqn. 9 is bounded above by TodH2VTTTogool +T)6) log(1 + T/d)).
C.3 Proof for Lemma 4.4
Lemma (Lemma 4.4 restated). With probability at least 26, where 5 2 74. Term (iii) in Eqn. (9)
bounded by O 2 v dT log H) log(1 + )
Proof. Term (iii) reflects the portion of regret attributable to inaccuracies in estimating the true parameter O Let θ,-1 == arg maxeec, R(Tri Xx, O, f). By definition,
R(mAX, X,, 0x-1,
Fxz 1. Fx:,
By Eqn. (23). we demonstrate that Term (iii) in can be split into two parts corresponding the cumulative estimation error of 0f (see Terms and in (23) and the cumulative estimation error of di (see Term 3 in (23). Recall that 0 is variant of the online Newton estimator (see Algorithm defined by
0 arg min 1 |e
0 + (0- 05-1 vi.(0=-1))
12;
where -
+ and V -V--+ 3xx, 3 5f. is the truncated observation of yf Because y follows a Poisson distribution and is linear 9,, it special case of heavy- tailed distribution with bounded second moment. Consequently, Lemma B.3 can be used to construct high-confidence bound on 0,, which in turn controls Terms and 2 in Eqn. 23
26

---

Term (iii)
Σ OPT (x,
E -E Na Σ R ( 0, F...)
=B
Σ
Thi O--11 (..1 - R (T; (
0, 0,
T
11
Σ ( Ahe xi)
0, - Ti;
Σn
=2
Pin
V1=1
tur
H
E
E
(0
x1)(1
- (A,, x1)) + (005)) x1) - Dr x1 (AA
,x))
"(A,, xi1)
5h,2""
hml
R Te; X,, O, ..%%11)) where A = x5, x()
ET pp
T
H
0s,,1 + dss (0 (05).2:30 xxi - d--1 (0'7) xxح|
(0--1 Sh.1
E
11
-Ogi, xx)
+BA BB 100-- 8/. -Os xii + R-1 dsr.
B₂BB))
5%
T=
H
E
(
(
0 0-1
01_1 S
03h x()
St
5%
Term 1
H
B
E
0 0'-1
0 Ost xiil|
$
5/22
Term
T
11
+ B
E
7-1
g 1-1
+
36-1
dsh.
1
Term
(23)
To bound Term in Eqn. 23 we first introduce n/, where
n == [ [H] Sh,1 13/:n1 s H.
27

---

Then we have the following inequality:
T
1-
+
--
1 xx)
(0's
-0--1
+
+--11
-ss xii
5/.1
5h
Sh11
T
S 2E
Σ
Σ
n
11xell
1= IEW
(24)
$ 2H
|
[xell(v
(25)
1=7 IEH
$ 2H
Xx
sellivv
1EH
1=
(26)
S VaH2O
(1
44TH
log
1 +
T 2d
(27)
Let us denote
7 110%
0s lly We obtain Eqn. 24 by rearranging terms in the
expression involving 0 with same I. We use the fact that nł < H to get Eqn. 25 Next, we apply the Cauchy-Schwarz inequality to derive Eqn. (26). By Lemma 3.3 we know that, with probability at least 1 - 6. n < for all / 1, with defined in Lemma 3.3 In addition, we use Lemma 11 of
Abbasi- Yadkori et al. 2011 to bound Σ ||x I1 [lcv yielding
x livv
S
log
det(Vr det(V.)
< 4d log 1+ 2d
Combining these results and applying the union bound gives us Eqn. (27 Similarly, by an analogous argument, show that, with probability at least 6, Term 2 in Eqn. 23 satisfies similar bound, as shown below.
vaHro ( T
Σ
E
05-1 Sh +
09 xii| s
4TH 8
log
1
T 2d
St.2
The principal difficulty in designing Algorithm lies in estimating d/. which captures the long-term impact of advertising on product conversion. Since di always appears alongside O, in the model
yi, Poi(d: ds 0 xx). the main technical challenge is establishing high-probability bound on Id; dil that leverages the estimation error of oz. Theorem 4.1 summarizes our results in this direction. By
Theorem 4. know that given > Hny and where
H1, with probability 5, J.z di D/.
4H Ba / d log + t + 2e Ba B, Bg log(?) 2)
Dj d (0.
[o. Bal 11 -d <
b
VNu
Therefore, by applying the union bound to make results valid Vt [T' and Hmg VI H,, have that for 2 :r, we conclude that with probability at least Term (3) in Eqn. 23 can be bounded above by
28

---

E
d=11 Sh.1
8 5
dsg..
M==1
8H Bd log( 1 + 2d) 7 +
2e Bd B. Bo log
2)) E
H Nr.
1 Vt + Oloog( HT)) (28)
b
T 2d
4HT
2H
0 HTVdTllo log 1
log
log
(29)
Equation (8) follows by gathering all terms involving the same of d,. Next, we obtain Equation (29 by noting that Σ Nr.1 T H. Combining the above results, we conclude that, with probability at least 1 - 25 (where 5 2 Tta). ) Term (iii) in Eqn.
( is bounded by
ol12 v dT log =) log(1 1 + 27
C.4 Proof of Lemma 4.5
Lemma (Lemma 4.5 restated). With probability at least - with 82 A. O G,
Proof.
2 T, Ch Hy E Dj}) P -, H.
P
H1, E D
= (MMM):::eee...))))))))()(M.M E E Di)) Hi, D13)
> 1 P ((
By Lemma 3.3
we have
IP ((((V) 2 Y2 H. O2 E c))) S Σ
P T 01 $ Ct 5.
LeN
Moreover, by Theorem
4.1 with 8 2 HT we have
P (((4 v H, D(1)))
Σ
P(d & D < HT8.
IEH1 TE[T]
Combining these results together, we have with probability at least 1 1-6 with 5 82 3.. θ E C, Vt.
D Technical Lemmas
Lemma D.1 (Sub-Exponentiality of Poisson Random Variable). X Poi(u), then the centered random variable X - y is SubE(ep, 1). Equivalently, there exist constants v² ej and a = 1 such
that, all [t] < 1/a 1, (Xe(((=w) < exp(21 (2 = exp(e)t?).
Proof. Below is the proof showing that a Poisson(μ) random variable is sub-exponential with parameters (eμ, 1). The proof hinges on bounding the moment-generating function (MGF) of the centered random variable X μ.. Recall that if X ~ Poi(μ), its moment-generating function (MGF)
E E exp(ule' - -1)).
For the centered random variable X 14,
t [[e explule' -1-t))
29

---

We claim that, for all [t] S
e' - et
Indeed, expanding e in its Taylor series about
12
13
1.2
1
e' = 1 + t
e¹ -
+
+
2
2
1, this of higher-order terms is bounded above by constant times 12, A convenient choice is e, giving
For |4| <
1 - eta
Combining the two steps, for |t| I 1,
E E[eA(-HH) [i] explule' -x & explu-et
Therefore, X J satisfies
E [[(!(X-H) s exp(ex(1) for all 14| < 1.
By definition, this means X is SubE(eu,1).
Lemma D.2 (Theorem in Abbasi- Yadkori al. (011)). Assume the same in Theorem D.3 let Eg = ATa, X > 0. Define Yt x, B + Tt, with т) defined in Lemma D.3 and assume that || B3, ||x||22 < B Then, for any 5 0, with probability at least for all t 0, B lies
in the set
C-= c=-BE
1 1+1B2/A)
+ VABB !
BE BERR 113t - -B11,, S 50² dlog
where 3r = (Eir )al)
EE X.Y.)
Lemma D.3 (Theorem in Abbasi- Yadkori et al. (011)). Let (Fi) be filtration. Let {ne te be a real-valued stochastic process such that 1p is Fr F.mesuurabll and th conditionally o² -s-sub- Gaussian for some o² O. Let (x, ) be
-vauud stochastic process such that x₃ is Ft-1 measurable. Assume that Eg is a d x positive definite matrix. For any 2 0, define Σ, = Et-1 + x and S₁ = ES=1 N1x Then for any ō > O, with probability at least for all t 2 0, we have ||S.1|2, I 20 2og (V de
det /6)
Lemma D.4 (Sub-exponential tail bound). Suppose X sub-exponential with parameters (v², at). Then
eexp 2x) if <
P(IX - x)
2 2exp( ( for t
2021 ). Consider random variable X, ~ SE(v? a) and 3 is Lemma D.5 (Lemma in Hao et al.
a non-zero sealar, then BX; SE(3 Dz
3la)
Lemma D.6 (Lemma in Hao SE(1?, for = I,...,7, n. then X 1= X, follows SE (Eiz) V?? max; as).
2021 ). Consider independent random variables X;
D.1 Proof of Fact 2.7
Proof. In this section, we prove that the tuple A, Px: (R), A, tutes Contextual Markov decision process (CMDP) by demonstrating that satisfies the Markov property.
at, x;) x;) $1, H) consti-
If we lose the bid, then we have
P (RR = dsg 1.1 (0s; 1.2" (1 - Fu Fati(a/+1, + (10s), xx) PPtti (h+11aha1:x))) Fut Fatilabui::/
Shan (S), + 1, st 15, añ, RK,,... ot. ab) = 1 Fr, Fajai,,1)) xx).
30

---

If we win the bid, then we have
R = - (0
x1) - Fit1 +1)+1: + (10 xx) - (a+1(ah++::0)) F x(),
Sh = (1, 1) a. R ab)) = Fi xx)-
From the above equation, we notice that
IP (R)+1 1h ab. ri...., St a/,) P (R)+1: Sh111h a).)
Therefore, the Markov property holds and the model is CMDP.
31

---

NeurIPS Paper Checklist
The checklist is designed encourage best practices for responsible machine learning research, addressing issues of reproducibility, transparency, research ethics, and societal impact. Do not remove the checklist: The papers not including the checklist will be desk rejected. The checklist should follow the references and follow the (optional) supplemental material. The checklist does NOT count towards the page limit.
Please read the checklist guidelines carefully for information on how to answer these questions. For each question in the checklist:
You should answer [Yes], [No]. or [NA].
[NA] means either that the question Not Applicable for that particular paper or the relevant information is Not Available.
Please provide short (1-2 sentence) justification right after your answer (even for NA).
The checklist answers are an integral part of your paper submission. They are visible to the reviewers, area chairs, senior area chairs, and ethics reviewers. You will be asked to also include (after eventual revisions) with the final version of your paper, and its final version will published with the paper.
The reviewers of your paper will be asked use the checklist as one of the factors their evaluation. While "[Yes] is generally preferable to "[No]" ", it is perfectly acceptable to answer "[No] providedd proper justification is given (e.g.. "error bars are not reported because it would be too computationally expensive" or "we were unable to find the license for the dataset we used"). In general, answering binary way, we
"[No] or "[NA]" is not grounds for rejection. While the questions are phrased acknowledge that the true answer is often more nuanced, please just use your best judgment and write justification to elaborate. All supporting evidence can appear either in the main paper or the supplemental material, provided in appendix. If you answer [Yes] to a question, in the justification please point to the section(s) where related material for the question can be found.
IMPORTANT, please:
Delete this instruction block, but keep the section heading "NeurIPS Paper Checklist",
Keep the checklist subsection headings, questions/answers and guidelines below.
Do not modify the questions and only use the provided macros for your answers.
1. Claims
Question:
Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification:
It summarizes the main contribution discussed at the end of Section I]
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results be expected to generalize other settings.
is fine include aspirational goals as motivation as long is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors? Answer: [Yes]
Justification: Please refer Section Discussion.
32

---

Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create a separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, c.g., if the approach was only tested few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails handle technical jargon.
The authors should discuss the computational efficiency the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory assumptions and proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
Justification: Please refer to Appendix.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced in the statement of any theorems.
The proofs can either appear in the main paper the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should complemented by formal proofs provided in appendix supplemental material.
Theorems and Lemmas that the proof relies upon should properly referenced.
4. Experimental result reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that it affects the main claims and/or conclusions the paper (regardless whether the code and data are provided or not)?
Answer: [NA]
Justification:
We did not include experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
33

---

If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. w
For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution is specific model and empirical evaluation, it may be necessary to either make it possible for others to replicate the model with the same dataset, or provide access the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access a hosted model (e.g., in the case of a large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurlPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make it clear how to reproduce that algorithm. (b) the contribution is primarily a new model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [NA]
Justification:
No real-world data included in the current version.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (nttps://niis.co cc/
for more details.
While we encourage the release of code and data, we understand that this might not be possible, so "No" an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https
/ /ttppp.cc/pbllc/guudeeee http://oeesuiiiiinoooooooooooooo
for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
34

---

Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental setting/details
Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Question:
Answer: [NA]
Justification: Not applicable.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented the core the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, supplemental material.
7. Experiment statistical significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [NA]
Justification: Not applicable.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results accompanied by error bars, confi- dence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g.. Normally distributed errors).
It should be clear whether the error bar is the standard deviation or the standard error of the mean.
OK to report 1-sigma error bars, but one should state The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that out of range (e.g. negative error rates).
If error bars reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables the text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [NA]
Justification: Not applicable.
Guidelines:
The answer NA means that the paper does include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
35

---

The paper should provide the amount of compute required for each of the individual experimental runs as well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make into the paper).
9. Code of ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics
Answer: [NA]
Justification: Not applicable.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require a deviation from the Code of Ethics.
The authors should make to preserve anonymity (e.g.. if there special consid- eration due to laws or regulations in their jurisdiction).
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [Yes]
Justification: Please refer Section I
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is a direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release models, providing defenses in addition attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility ML).
11. Safeguards
Question: Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, scraped datasets)?
Answer: [NA]
Justification: Not applicable.
Guidelines:
The answer NA means that the paper poses such risks.
36

---

Released models that have high risk for misuse or dual use should be released with necessary safeguards to allow for controlled use of the model. for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Are the creators original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [NA]
Justification: Not applicable.
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package dataset.
The authors should state which version of the asset used and, if possible, include URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswi thcode. com datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re- re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
If this information is not available online, the authors are encouraged to reach out to the asset's 's creators.
13. New assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification: Not applicable.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/model as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and research with human subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification: Not applicable.
37

---

Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included the main paper.
According to the NeurIPS Code Ethics, workers involved in data collection, curation, other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional review board (IRB) approvals or equivalent for research with human subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: Not applicable.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent)
may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and expect authors to adhere to the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
16. Declaration of LLM usage
Question: Does the paper describe the usage of LLMs if it is an important, original, or non-standard component of the core methods this research? Note that if the L.M used only for writing, editing, or formatting purposes and does not impact the core methodology. scientific rigorousness, or originality the research, declaration is not required.
Answer: [NA]
Justification: All theorems are developed by human not LLM.
Guidelines:
The answer NA means that the core method development in this research does not involve LLMs any important, original, non-standard components.
Please refer to our L.M policy (https: http:p/://errrpps.cccoooeeeeeeee for what should or should not be described.
38


Reviews:
[{"review_id": "R8isG60svX", "reviewer": "Reviewer_1MCA", "summary": "The paper addresses the challenge of modeling and optimizing online advertising bids by integrating delayed rewards, cumulative ad impacts, and customer heterogeneity. It formulates ad bidding as a Contextual Markov Decision Process (CMDP) with delayed Poisson rewards and proposes a two-stage maximum likelihood estimator combined with a reinforcement learning algorithm to derive personalized bidding strategies.", "questions": "NA", "limitations": "NA", "rating": 3, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths:\n1. It is interesting to modeling the online advertising problem through Contextual MDP.\n2. Concrete theoretical proofs for the regret bound.\n\nWeaknesses:\n1. As the motivation of this work is the online advertising problem, the empirical experiments seem to be necessary. Basically, it is hard to determine whether the assumption about the conversion rate is reasonable.", "was_revised": true, "final_justification": "I shall keep my score.", "rebuttal": "We appreciate the reviewer’s support for our theoretical analysis. Due to the sensitivity and non-disclosure of real-world bidding data, such data is unfortunately rarely available—explaining why many prior works lack real-world evaluations. Nonetheless, following the reviewer's comment,  we have conducted synthetic study during the rebuttal period: (1) our algorithm achieves near-optimal regret scaling of $\\sqrt{T}$ in empirical studies, and (2) it substantially outperforms baseline policies such as aggressive bidding, passive bidding, and a random bidding policy. We hope this additional empirical evidence could mitigate the reviewer's concerns and encourage the reviewer to re-consider our paper’s rating evaluation accordingly.\n\n**Environment Setup**: We simulate a second-price auction with horizon $H = 3$ (a reasonable horizon length since in reality advertisers show their ads only a few times to each Internet user), context dimension $D = 2$, and $T = 20,000$ sequential customers. The first 2,400 rounds are for exploration; the rest for exploitation. Context vectors $x_t \\in \\mathbb{R}^2, d_l, \\beta_h, \\sigma_h$ are sampled elementwise from $|\\mathcal{N}(0,1)| + 0.1$, ensuring positivity. Parameters $\\theta_l  \\sim 5 \\cdot |\\mathcal{N}(0,1)| + 0.1$. Note that under our current simulation setting, an impression brings on average an instantaneous reward that is around 5 times than its cost (i.e. HOB price). Moreover, the reward of the impression decays quickly with time. These suggest that an aggressive bidding strategy (i.e. try to always win the bid and get the impression) is actually close to the optimal bidding strategy and thus serves as a competitive baseline policy.\n\n**Estimators**: We estimate four categories of parameters. $\\theta_l$ is learned using an online Newton method (Algorithm 3) with truncation threshold $\\tau = 100{,}000$, bound $B_\\theta = 10$, zero initialization, and $V_0 = I$. The delay impact $d_l$ is estimated via a two-stage MLE (Eq. 3) using $D_{t,l}$, $\\hat{\\theta}_l$, and $x_t$. $\\beta_h$ is estimated by ridge regression (Eq. 5, $\\lambda = 1.0$), and $\\sigma_h$ via empirical variance (Eq. 6). As $\\theta_l$ and $d_l$ are the most critical, we provide the corresponding code in the appendix.\n\n**Connection Between Bid Amount, Auction Outcome, and Realized Reward**: In our setting, the bidder's action is the bid amount, but due to the second-price auction format, the reward depends only on the outcome–whether the bid exceeds the highest other bid (HOB)-not the bid itself. Winning results in paying the HOB; losing incurs no cost. This decoupling allows optimal rewards to be computed from outcomes rather than bids.\nWe leverage this to evaluate both oracle and policy-based rewards. With full knowledge of true parameters, we enumerate all $2^H = 8$ possible win/loss outcomes across $H = 3$ rounds and define the **oracle reward** as the maximum achievable. With estimated parameters, we compute the expected reward for each outcome and choose the best sequence (Algorithm 1), which is then run through the simulator to obtain the realized reward. Regret is defined as the cumulative gap between oracle and actual rewards, reflecting errors from estimation and suboptimal bidding.\n\n**Simulation and Regret**\n1. Sample ground-truth parameters $(\\theta_l, d_l, \\beta_h, \\sigma_h)$, which remain fixed. Initialize estimates $(\\hat{\\theta}_l, \\hat{d}_l, \\hat{\\beta}_h, \\hat{\\sigma}_h)$ using default values (e.g., zeros or identity).\n2. Simulate $T = 20{,}000$ customers over two phases: exploration (first 2,400 rounds) and exploitation (remaining 17,600 rounds).\n3. Exploration Phase: Uniformly sample each of the $2^H = 8$ bidding outcome sequences across 2,400 rounds (300 per outcome). For each round: Sample context $x_t$; simulate reward and HOB under the chosen bidding outcome; Compute and record the oracle reward; Store observations for estimation; Apply data splitting to update parameter estimates.\n4. Exploitation Phase: For each round: Observe $x_t$; compute estimated rewards for all 8 bidding sequences using current estimates; Select the best sequence; simulate reward; compute oracle reward and reward gap; Update estimates via data splitting.\n5. Return cumulative regret as $np.cumsum(reward_{diff})$.\n\n**Baseline Policies**: We compare against three baselines. **Aggressive  bidding:** This simulates the strategy that the firm actively engages in winning ad impressions by consistently offering the highest bidding price (and pays second best price). In other words, the firm always wins by bidding above the HOB $(o_t = [1, 1, 1])$; **Bidding at random:** Sample $o_t$ uniformly from all 8 bidding outcomes and set bids accordingly; **Passive bidding:** This simulates the strategy that the firm rarely engages in the ad impression bidding war, where it gives very low bidding or simply does not bid $(o_t = [0, 0, 0])$.\n\nRegret for each is computed using the same oracle-based metric, serving as benchmarks for our algorithm.\nWe remark here again that due to our simulation setting, the aggressive bidding strategy is close to the optimal strategy. Therefore, it serves as a competitive benchmark, though it obviously suffers a O(T) regret since it is a fixed policy without any learning.\n\nWe run our proposed algorithm alongside the three baseline policies over 20 independent trials. The table below reports the average cumulative regret with ±0.5 standard deviation for all four algorithms. The last row shows the estimated regret order, obtained by applying a log-log transformation followed by linear regression. As shown, our algorithm achieves a fitted regret order of 0.37, while all three baselines exhibit linear regret. These results are consistent with our theoretical analysis and demonstrate the superior performance of our approach and the importance of learning.\n| Round   | Our Algorithm                 | Aggressive Bid              | Random Bid                   | Passive Bid                    |\n|---------|----------------------------|-----------------------------|------------------------------|-------------------------------|\n| 500     | 1770 [1174, 2379]          | 228 [121, 336]              | 1920 [1791, 2049]            | 4630 [3391, 5869]             |\n| 5000    | 8465 [5585, 11345]         | 2373 [1243, 3502]           | 19285 [17873, 20697]         | 46179 [33850, 58508]          |\n| 10000   | 8484 [5606, 11363]         | 4741 [2477, 7005]           | 38399 [35573, 41226]         | 92468 [67735, 117201]         |\n| 15000   | 8505 [5628, 11382]         | 7142 [3724, 10561]          | 57651 [53452, 61849]         | 138652 [101576, 175729]       |\n| 20000   | 8525 [5649, 11401]         | 9568 [4991, 14146]          | 76945 [71390, 82500]         | 184873 [135414, 234332]       |\n| **Fitted Order** | **0.37**                 | **1.0**                    | **1.0**                      | **1.0**                        |\n\n\n**Appendix**\n\nDue to space constraints, additional codes and results are available upon request.\n\n```python\nclass ThetaEstimator:\n    def truncate_payoff(self, y, x, V, tau):\n        norm_x_V = np.sqrt(x.T @ V @ x); return y if norm_x_V * abs(y) < tau else 0.0\n    def gradient_term(self, y, x, theta):\n        return (-y + x @ theta) * x\n    def constrained_quad_solver(self, theta0, V, k, b, tol=1e-6, max_iter=100):\n        d = len(theta0)\n        def phi(lambda_):\n            A = V + 2 * lambda_ * np.eye(d); rhs = -k - 2 * lambda_ * theta0; return np.linalg.solve(A, rhs)\n        def constraint(lambda_):\n            phi_val = phi(lambda_); theta = theta0 + phi_val; return norm(theta) - b\n        try:\n            phi0 = np.linalg.solve(V, -k); theta_unconstrained = theta0 + phi0\n            if norm(theta_unconstrained) <= b: return theta_unconstrained\n        except: pass\n        l, r = 0.0, 1e6\n        for _ in range(max_iter):\n            m = (l + r) / 2\n            if constraint(m) > 0: l = m\n            else: r = m\n            if r - l < tol: break\n        return theta0 + phi(r)\n    def run_estimation_by_state(self, W_t_l, true_theta_l, X_t_l, theta_l_hat, V_l, tau=10, radius=1):\n        error_l = {l: [] for l in W_t_l}\n        for l, observations in W_t_l.items():\n            for (round_idx, y_raw) in observations:\n                x_t = X_t_l[l][round_idx]; y_t = self.truncate_payoff(y_raw, x_t, V_l[l], tau)\n                k_t = self.gradient_term(y_t, x_t, theta_l_hat[l]); theta_next = self.constrained_quad_solver(theta_l_hat[l], V_l[l], k_t, radius)\n                V_l[l] += np.outer(x_t, x_t); theta_l_hat[l] = theta_next\n                error = norm(theta_next - true_theta_l[l]) ** 2; error_l[l].append(error)\n        return V_l, theta_l_hat, error_l\nclass DelayImpactEstimator:\n    def __init__(self, d_true):\n        self.d_true = d_true; self.num = {l: 0.0 for l in d_true}; self.denom = {l: 0.0 for l in d_true}; \n        self.d_hat = {l: [] for l in d_true}; self.errors = {l: [] for l in d_true}; \n        self.latest_d_hat = {l: np.nan for l in d_true}\n    def run_update(self, D_t_l, x, theta_hat):\n        self.theta_hat = theta_hat\n        for l in D_t_l:\n            for h, S2, y in D_t_l[l]:\n                key = str(S2) if str(S2) in self.theta_hat else int(S2)\n                theta = self.theta_hat[key]\n                self.num[l] += y; self.denom[l] += np.dot(theta, x)\n            d_hat = self.num[l] / self.denom[l] if self.denom[l] != 0 else np.nan\n            self.d_hat[l].append(d_hat); self.latest_d_hat[l] = d_hat\n            error = (d_hat - self.d_true[l]) ** 2 if not np.isnan(d_hat) else np.nan\n            self.errors[l].append(error)\n        return self.latest_d_hat"}, {"review_id": "3hHwJiHbdM", "reviewer": "Reviewer_uxuX", "summary": "This paper tackles the problem of optimizing online ad bidding strategies by creating a model that, unlike previous work, simultaneously accounts for three real-world complexities: 1) the delayed impact of ads on customer purchases, 2) the cumulative effects of repeated ad exposure, and 3) customer heterogeneity. To achieve this, the authors make the following key contributions: They model the ad bidding problem as a CMDP with delayed Poisson rewards. The \"contextual\" aspect allows for personalized strategies, while the MDP structure captures cumulative effects over time. They introduce a novel and efficient two-stage maximum likelihood estimator with a data-splitting strategy. This allows them to learn the parameters of their complex model online while carefully controlling for estimation errors caused by the delayed rewards. Based on this estimation method, they design a reinforcement learning algorithm that learns personalized bidding policies and prove that it achieves a near-optimal theoretical regret bound.", "questions": "1. The paper is entirely theoretical. Could you please justify this choice? While the theoretical results are strong, the absence of simulations makes it difficult to gauge the practical performance of the proposed algorithm. My evaluation would improve significantly if you could provide even a small-scale simulation study on synthetic data. \n\n2. The model relies on several specific parametric assumptions. How sensitive do you expect your theoretical results and your proposed algorithm to be if these assumptions are violated, as they likely would be in a real-world setting?", "limitations": "yes", "rating": 4, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 3, "significance": 2, "originality": 3, "strengths_and_weaknesses": "Strengths\n1. The paper tackles a highly significant and practical problem in computational advertising. Its primary contribution is the novel and unified CMDP framework that, for the first time, jointly models the crucial dynamics of delayed rewards, cumulative ad effects, and user heterogeneity.\n\n2. The technical quality of the paper is exceptionally high. The main theoretical contribution—the development of the two-stage MLE for online estimation under delayed Poisson rewards—is sophisticated and rigorously analyzed.\n\n3. The paper is well-written, clearly structured, and does an excellent job of motivating the problem by highlighting the limitations of existing approaches.\n\nWeakness\n\nThe most significant weakness of the paper is the complete absence of empirical results. The work is purely theoretical, with no simulations or experiments on real or synthetic data. While the theoretical guarantees are strong, this omission makes it impossible to assess the practical performance of the algorithm and the real-world magnitude of the constants hidden in the regret bound and the robustness of the method to violations of its underlying assumptions.", "was_revised": true, "final_justification": "The author provided simulation results in their rebuttal and show the performance compared with other baselines.", "rebuttal": "Thank you for the positive feedback and the suggestion to include synthetic simulations. In response, we conducted experiments during the rebuttal period with two main findings: (1) our algorithm achieves near-optimal regret scaling of $\\sqrt{T}$; (2) it substantially outperforms several baseline policies such as aggressive bidding, passive bidding, and a bidding at random strategy. We hope this additional empirical evidence could mitigate the reviewer's concerns and encourage the reviewer to re-consider our paper’s rating evaluation.\n\n**Environment Setup**: We simulate a second-price auction with horizon $H = 3$ (a reasonable horizon length since in reality advertisers show their ads only a few times to each Internet user), context dimension $D = 2$, and $T = 20,000$ sequential customers. The first 2,400 rounds are for exploration; the rest for exploitation. Context vectors $x_t \\in \\mathbb{R}^2, d_l, \\beta_h, \\sigma_h$ are sampled elementwise from $|\\mathcal{N}(0,1)| + 0.1$, ensuring positivity. Parameters $\\theta_l  \\sim 5 \\cdot |\\mathcal{N}(0,1)| + 0.1$. Note that under our current simulation setting, an impression brings on average an instantaneous reward that is around 5 times than its cost (i.e. HOB price). Moreover, the reward of the impression decays quickly with time. These suggest that an aggressive bidding strategy (i.e. try to always win the bid and get the impression) is actually close to the optimal bidding strategy and thus serves as a competitive baseline policy.\n\n**Estimators**: We estimate four categories of parameters. $\\theta_l$ is learned using an online Newton method (Algorithm 3) with truncation threshold $\\tau = 100{,}000$, bound $B_\\theta = 10$, zero initialization, and $V_0 = I$. The delay impact $d_l$ is estimated via a two-stage MLE (Eq. 3) using $D_{t,l}$, $\\hat{\\theta}_l$, and $x_t$. $\\beta_h$ is estimated by ridge regression (Eq. 5, $\\lambda = 1.0$), and $\\sigma_h$ via empirical variance (Eq. 6). As $\\theta_l$ and $d_l$ are the most critical, we provide the corresponding code in the appendix.\n\n**Connection Between Bid Amount, Auction Outcome, and Realized Reward**: In our setting, the bidder's action is the bid amount, but due to the second-price auction format, the reward depends only on the outcome–whether the bid exceeds the highest other bid (HOB)-not the bid itself. Winning results in paying the HOB; losing incurs no cost. This decoupling allows optimal rewards to be computed from outcomes rather than bids.\nWe leverage this to evaluate both oracle and policy-based rewards. With full knowledge of true parameters, we enumerate all $2^H = 8$ possible win/loss outcomes across $H = 3$ rounds and define the **oracle reward** as the maximum achievable. With estimated parameters, we compute the expected reward for each outcome and choose the best sequence (Algorithm 1), which is then run through the simulator to obtain the realized reward. Regret is defined as the cumulative gap between oracle and actual rewards, reflecting errors from estimation and suboptimal bidding.\n\n**Simulation and Regret**\n1. Sample ground-truth parameters $(\\theta_l, d_l, \\beta_h, \\sigma_h)$, which remain fixed. Initialize estimates $(\\hat{\\theta}_l, \\hat{d}_l, \\hat{\\beta}_h, \\hat{\\sigma}_h)$ using default values (e.g., zeros or identity).\n2. Simulate $T = 20{,}000$ customers over two phases: exploration (first 2,400 rounds) and exploitation (remaining 17,600 rounds).\n3. Exploration Phase: Uniformly sample each of the $2^H = 8$ bidding outcome sequences across 2,400 rounds (300 per outcome). For each round: Sample context $x_t$; simulate reward and HOB under the chosen bidding outcome; Compute and record the oracle reward; Store observations for estimation; Apply data splitting to update parameter estimates.\n4. Exploitation Phase: For each round: Observe $x_t$; compute estimated rewards for all 8 bidding sequences using current estimates; Select the best sequence; simulate reward; compute oracle reward and reward gap; Update estimates via **data splitting**.\n5. Return cumulative regret as $np.cumsum(reward_{diff})$.\n\n**Baseline Policies**: We compare against three baselines. **Aggressive  bidding:** This simulates the strategy that the firm actively engages in winning ad impressions by consistently offering the highest bidding price (and pays second best price). In other words, the firm always wins by bidding above the HOB $(o_t = [1, 1, 1])$; **Bidding at random:** Sample $o_t$ uniformly from all 8 bidding outcomes and set bids accordingly; **Passive bidding:** This simulates the strategy that the firm rarely engages in the ad impression bidding war, where it gives very low bidding or simply does not bid $(o_t = [0, 0, 0])$.\n\nRegret for each is computed using the same oracle-based metric, serving as benchmarks for our algorithm.\nWe remark here again that due to our simulation setting, the aggressive bidding strategy is close to the optimal strategy. Therefore, it serves as a competitive benchmark, though it obviously suffers a O(T) regret since it is a fixed policy without any learning.\n\nWe run our proposed algorithm alongside the three baseline policies over 20 independent trials. The table below reports the average cumulative regret with ±0.5 standard deviation for all four algorithms. The last row shows the estimated regret order, obtained by applying a log-log transformation followed by linear regression. As shown, our algorithm achieves a fitted regret order of 0.37, while all three baselines exhibit linear regret. These results are consistent with our theoretical analysis and demonstrate the superior performance of our approach and the importance of learning.\n| Round   | Our Algorithm                 | Aggressive Bid              | Random Bid                   | Passive Bid                    |\n|---------|----------------------------|-----------------------------|------------------------------|-------------------------------|\n| 500     | 1770 [1174, 2379]          | 228 [121, 336]              | 1920 [1791, 2049]            | 4630 [3391, 5869]             |\n| 5000    | 8465 [5585, 11345]         | 2373 [1243, 3502]           | 19285 [17873, 20697]         | 46179 [33850, 58508]          |\n| 10000   | 8484 [5606, 11363]         | 4741 [2477, 7005]           | 38399 [35573, 41226]         | 92468 [67735, 117201]         |\n| 15000   | 8505 [5628, 11382]         | 7142 [3724, 10561]          | 57651 [53452, 61849]         | 138652 [101576, 175729]       |\n| 20000   | 8525 [5649, 11401]         | 9568 [4991, 14146]          | 76945 [71390, 82500]         | 184873 [135414, 234332]       |\n| **Fitted Order** | **0.37**                 | **1.0**                    | **1.0**                      | **1.0**                        |\n\n\n---\n**Appendix**\n\nDue to space constraints, additional codes and results are available upon request.\n\n```python\ndef data_splitting(results):\n    W_t_l = {}; D_t_l = {}\n    for result in results:\n         h = result['round']; s1 = result['S1']; s2 = result['S2'];o_t = result['o_t'];y = result['y_t']\n         if o_t == 1:\n            l = s1;W_t_l.setdefault(l, []).append((h, y))\n         else:\n            if s1 == 'inf':\n               W_t_l.setdefault('-inf', []).append((h, y))  # For θ_{-inf}\n            else:\n               l = s1;D_t_l.setdefault(l, []).append((h, s2, y))\n    return W_t_l, D_t_l\nclass ThetaEstimator:\n    def truncate_payoff(self, y, x, V, tau):\n        norm_x_V = np.sqrt(x.T @ V @ x); return y if norm_x_V * abs(y) < tau else 0.0\n    def gradient_term(self, y, x, theta):\n        return (-y + x @ theta) * x\n    def constrained_quad_solver(self, theta0, V, k, b, tol=1e-6, max_iter=100):\n        d = len(theta0)\n        def phi(lambda_):\n            A = V + 2 * lambda_ * np.eye(d); rhs = -k - 2 * lambda_ * theta0; return np.linalg.solve(A, rhs)\n        def constraint(lambda_):\n            phi_val = phi(lambda_); theta = theta0 + phi_val; return norm(theta) - b\n        try:\n            phi0 = np.linalg.solve(V, -k); theta_unconstrained = theta0 + phi0\n            if norm(theta_unconstrained) <= b: return theta_unconstrained\n        except: pass\n        l, r = 0.0, 1e6\n        for _ in range(max_iter):\n            m = (l + r) / 2\n            if constraint(m) > 0: l = m\n            else: r = m\n            if r - l < tol: break\n        return theta0 + phi(r)\n    def run_estimation_by_state(self, W_t_l, true_theta_l, X_t_l, theta_l_hat, V_l, tau=10, radius=1):\n        error_l = {l: [] for l in W_t_l}\n        for l, observations in W_t_l.items():\n            for (round_idx, y_raw) in observations:\n                x_t = X_t_l[l][round_idx]; y_t = self.truncate_payoff(y_raw, x_t, V_l[l], tau)\n                k_t = self.gradient_term(y_t, x_t, theta_l_hat[l]); theta_next = self.constrained_quad_solver(theta_l_hat[l], V_l[l], k_t, radius)\n                V_l[l] += np.outer(x_t, x_t); theta_l_hat[l] = theta_next\n                error = norm(theta_next - true_theta_l[l]) ** 2; error_l[l].append(error)\n        return V_l, theta_l_hat, error_l\nclass DelayImpactEstimator:\n    def __init__(self, d_true):\n        self.d_true = d_true; self.num = {l: 0.0 for l in d_true}; self.denom = {l: 0.0 for l in d_true}; \n        self.d_hat = {l: [] for l in d_true}; self.errors = {l: [] for l in d_true}; \n        self.latest_d_hat = {l: np.nan for l in d_true}\n    def run_update(self, D_t_l, x, theta_hat):\n        self.theta_hat = theta_hat\n        for l in D_t_l:\n            for h, S2, y in D_t_l[l]:\n                key = str(S2) if str(S2) in self.theta_hat else int(S2)\n                theta = self.theta_hat[key]\n                self.num[l] += y; self.denom[l] += np.dot(theta, x)\n            d_hat = self.num[l] / self.denom[l] if self.denom[l] != 0 else np.nan\n            self.d_hat[l].append(d_hat); self.latest_d_hat[l] = d_hat\n            error = (d_hat - self.d_true[l]) ** 2 if not np.isnan(d_hat) else np.nan\n            self.errors[l].append(error)\n        return self.latest_d_hat"}, {"review_id": "hiYQ0C49FA", "reviewer": "Reviewer_Xfce", "summary": "Motivated by the widely documented phenomenon of *recency bias*, the authors propose a reinforcement learning algorithm for efficient auto-bidding/ad placement which takes into consideration cumulative and delayed effects of prior advertising on user behaviour, rather than focusing solely on short-term engagement signals. Specifically, the auto-bidding decision process is modelled as a contextual MDP with delayed rewards represented through a Poisson distribution. The contextual factor allows for personalisation, accounting for preferences, seasonal factors etc., whilst the state captures the combined, long-term effect of multiple ads on the user over time. The authors note that prior work by Badanidiyuru et al. [2023] explores modeling the long-term effects of ads on users also via MDPs with Poisson rewards, however they assume homogenous treatment effects across the user-base, effectively ignoring personalisation as a factor in the outcome. This represents the first theoretical work on the design of bidding algorithms which addresses this factor alongside modeling delayed and cumulative ad impacts on users.\n\nA three-stage process is formulated for solving these MDPs. Firstly, an *exploration* stage, where ridge regression is used with variance estimators to estimate the transition dynamics. Secondly, an *exploitation* stage takes place which involves estimation of the advertisement effects. Finally, a two-stage likelihood estimator is developed by the authors in order to estimate the delayed advertisement effects. The latter approach is required due to two fundamental challenges, the non-concave nature of the log-likelihood, and the lack of closed form solutions to the scoring equations.\n\nThe contributions of the paper are theoretical, with the authors presenting proof of a near optimal regret bound for their algorithm. Evaluation on real-world data is left to future work, owing to the lack of publicly available online bidding datasets.", "questions": "**Q1** - Regarding the point raised in *Weaknesses* above regarding the background literature, could the authors please extend the discussion of prior work in the area in either the main text or appendix through additional text or a table briefly detailing competing approaches and their properties?\n\n**Q2** - As also mentioned prior, could the authors expand slightly on the impact of the decision on how the state should be formulated, and if possible, how much benefit extending the state from one to two or more recent ad exposures may have on performance? I understand here that this cannot yet be assessed empirically, however if there is other prior work which may point to an answer to this question, that would be useful detail to include.\n\nThese minor points would certainly improve the paper and I encourage the authors to address these points, however I feel that the contribution is strong regardless, and therefore recommend acceptance.", "limitations": "Yes", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 4, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "**Strengths**\n* Overall, the theoretical analysis carried out by the authors is thorough, and results in a near-optimal regret bound for online contextual RL with delayed Poisson rewards, which is a high quality and novel contribution to the literature. This contribution lays the groundwork for future work to explore the practical implementation of such an algorithm in real-world settings with online bidding datasets, likely by organisations which have access to such data on a large scale, as well as for additional theoretical contributions on considerations relevant to large-scale deployment such as budget constraints.\n* The authors present and introduce the background and problem setting clearly. Early in the paper, the work is placed clearly in the context of prior work in the area, with an intuitive explanation given of where this work offers a novel contribution compared to this prior work.\n* Whilst it’s difficult to categorically assign a very high level of significance to an approach which has been analysed theoretically before it has been evaluated in a real-world deployment setting, this approach does seem to have the potential for considerable impact. As the authors note themselves, this problem of learning to bid is highly challenging for a number of reasons, such as the heterogeneity of preferences across user bases on online services, the delayed nature of any feedback on such services, and the cumulative nature by which advertising impacts the behaviour of end users. The development of an effective approach to bidding which simultaneously tackles all of these concerns is a considerable step forward. \n\n**Weaknesses**\n* Whilst the discussion of background and prior work in the Introduction is clearly outlined, it is somewhat brief, limited to effectively around a single paragraph. Whilst of course space is always a limitation, I feel it would be helpful to include (or at least point to in the appendix), a slightly extended discussion or table listing the other referenced approaches to learning to bid, including brief details about the core of their approach and any obvious advantages/disadvantages relative to the proposed method.\n* One question which arose whilst reading the section discussing the state formulation was that whilst I fully understand the motivation for using only very recent ad exposures due to recency bias, I wondered whether there is any support/discussion in the literature surrounding only focusing on the single most recent advertising event. This is presented as the default choice for the algorithm in the paper, so although we’re not able to empirically assess the algorithm to check, if possible it would be useful to have some further discussion of how much useful information is gained by for example, extending the state formulation to the previous two ad exposures versus just the most recent one.", "was_revised": true, "final_justification": "I keep my original score unchanged, as whilst the clarifications and results provided by the authors in the rebuttal would improve the paper, they do not change my overall assessment of the work.", "rebuttal": "We sincerely appreciate the reviewer’s positive feedback on the originality of our work and the contribution of our theoretical development. We address the reviewer’s weakness and questions as below.\n\n**Adding a Discussion of Related Work in “Learning-to-Bid”**\n\nWe will add additional literature reviews following the suggestions. Due to space constraints in the rebuttal, we will include the additional references and discussion in the appendix of the revised manuscript.\n\n**On recency bias and impact of state formulation**\n\nAs we noted in the paper (Line 122), recency-based attribution is pretty much the default method in the industry for evaluating ad effectiveness, such as Google Auto Bidding. This idea is also supported by several psychology studies (Lines 118–120) that show people tend to be more influenced by recent experiences when making decisions. To the best of our knowledge, “Incrementality Bidding via Reinforcement Learning under Mixed and Delayed Rewards” is the only published work in “Learning-to-Bid” literature that incorporates a notion of “state” when modeling ad impact. However, that work assumes customer homogeneity and does not account for heterogeneity—one of the key limitations that our paper seeks to address.\n\nWe provide a detailed discussion in Appendix 1 on how the state formulation can be extended beyond the most recent ad exposure to incorporate domain knowledge. For instance, the state can include $n^t_h$, the total number of ads a customer has seen before round $h$. This opens the door to modeling richer exposure histories, such as the impact of last $k$ ad exposures. However, we acknowledge that directly modeling ad impact based on the past $k$ exposures is highly nontrivial. It introduces additional complexity due to mixture and delayed rewards as well as customer heterogeneity, making estimation significantly more difficult, and will leave it for future work.\n\n**Experiments**\n\nAs suggested by other reviewers, over this rebuttal period, we conducted a simulation to empirically verify our proposed algorithm, which we show that (1) our algorithm achieves near-optimal regret scaling of $\\sqrt{T}$, and (2) it substantially outperforms several baseline policies such as aggressive  bidding, passive bidding, and a bidding at random strategy. We include the results here for your reference.\n\n**Environment Setup**: We simulate a second-price auction with horizon $H = 3$ (a reasonable horizon length since in reality advertisers show their ads only a few times to each Internet user), context dimension $D = 2$, and $T = 20,000$ sequential customers. The first 2,400 rounds are for exploration; the rest for exploitation. Context vectors $x_t \\in \\mathbb{R}^2, d_l, \\beta_h, \\sigma_h$ are sampled elementwise from $|\\mathcal{N}(0,1)| + 0.1$, ensuring positivity. Parameters $\\theta_l  \\sim 5 \\cdot |\\mathcal{N}(0,1)| + 0.1$. Note that under our current simulation setting, an impression brings on average an instantaneous reward that is around 5 times than its cost (i.e. HOB price). Moreover, the reward of the impression decays quickly with time. These suggest that an aggressive bidding strategy (i.e. try to always win the bid and get the impression) is actually close to the optimal bidding strategy and thus serves as a competitive baseline policy.\n\n**Estimators**: We estimate four categories of parameters. $\\theta_l$ is learned using an online Newton method (Algorithm 3) with truncation threshold $\\tau = 100{,}000$, bound $B_\\theta = 10$, zero initialization, and $V_0 = I$. The delay impact $d_l$ is estimated via a two-stage MLE (Eq. 3) using $D_{t,l}$, $\\hat{\\theta}_l$, and $x_t$. $\\beta_h$ is estimated by ridge regression (Eq. 5, $\\lambda = 1.0$), and $\\sigma_h$ via empirical variance (Eq. 6). As $\\theta_l$ and $d_l$ are the most critical, we provide the corresponding code in the appendix.\n\n**Connection Between Bid Amount, Auction Outcome, and Realized Reward**: In our setting, the bidder's action is the bid amount, but due to the second-price auction format, the reward depends only on the outcome–whether the bid exceeds the highest other bid (HOB)-not the bid itself. Winning results in paying the HOB; losing incurs no cost. This decoupling allows optimal rewards to be computed from outcomes rather than bids.\nWe leverage this to evaluate both oracle and policy-based rewards. With full knowledge of true parameters, we enumerate all $2^H = 8$ possible win/loss outcomes across $H = 3$ rounds and define the **oracle reward** as the maximum achievable. With estimated parameters, we compute the expected reward for each outcome and choose the best sequence (Algorithm 1), which is then run through the simulator to obtain the realized reward. Regret is defined as the cumulative gap between oracle and actual rewards, reflecting errors from estimation and suboptimal bidding.\n\n**Simulation and Regret**\n1. Sample ground-truth parameters $(\\theta_l, d_l, \\beta_h, \\sigma_h)$, which remain fixed. Initialize estimates $(\\hat{\\theta}_l, \\hat{d}_l, \\hat{\\beta}_h, \\hat{\\sigma}_h)$ using default values (e.g., zeros or identity).\n2. Simulate $T = 20{,}000$ customers over two phases: exploration (first 2,400 rounds) and exploitation (remaining 17,600 rounds).\n3. Exploration Phase: Uniformly sample each of the $2^H = 8$ bidding outcome sequences across 2,400 rounds (300 per outcome). For each round: Sample context $x_t$; simulate reward and HOB under the chosen bidding outcome; Compute and record the oracle reward; Store observations for estimation; Apply data splitting to update parameter estimates.\n4. Exploitation Phase: For each round: Observe $x_t$; compute estimated rewards for all 8 bidding sequences using current estimates; Select the best sequence; simulate reward; compute oracle reward and reward gap; Update estimates via **data splitting**.\n5. Return cumulative regret as $np.cumsum(reward_{diff})$.\n\n**Baseline Policies**: We compare against three baselines. **Aggressive  bidding:** This simulates the strategy that the firm actively engages in winning ad impressions by consistently offering the highest bidding price (and pays second best price). In other words, the firm always wins by bidding above the HOB $(o_t = [1, 1, 1])$; **Bidding at random:** Sample $o_t$ uniformly from all 8 bidding outcomes and set bids accordingly; **Passive bidding:** This simulates the strategy that the firm rarely engages in the ad impression bidding war, where it gives very low bidding or simply does not bid $(o_t = [0, 0, 0])$.\n\nRegret for each is computed using the same oracle-based metric, serving as benchmarks for our algorithm.\nWe remark here again that due to our simulation setting, the aggressive bidding strategy is close to the optimal strategy. Therefore, it serves as a competitive benchmark, though it obviously suffers a O(T) regret since it is a fixed policy without any learning.\n\nWe run our proposed algorithm alongside the three baseline policies over 20 independent trials. The table below reports the average cumulative regret with ±0.5 standard deviation for all four algorithms. The last row shows the estimated regret order, obtained by applying a log-log transformation followed by linear regression. As shown, our algorithm achieves a fitted regret order of 0.37, while all three baselines exhibit linear regret. These results are consistent with our theoretical analysis and demonstrate the superior performance of our approach and the importance of learning.\n| Round   | Our Algorithm                 | Aggressive Bid              | Random Bid                   | Passive Bid                    |\n|---------|----------------------------|-----------------------------|------------------------------|-------------------------------|\n| 500     | 1770 [1174, 2379]          | 228 [121, 336]              | 1920 [1791, 2049]            | 4630 [3391, 5869]             |\n| 5000    | 8465 [5585, 11345]         | 2373 [1243, 3502]           | 19285 [17873, 20697]         | 46179 [33850, 58508]          |\n| 10000   | 8484 [5606, 11363]         | 4741 [2477, 7005]           | 38399 [35573, 41226]         | 92468 [67735, 117201]         |\n| 15000   | 8505 [5628, 11382]         | 7142 [3724, 10561]          | 57651 [53452, 61849]         | 138652 [101576, 175729]       |\n| 20000   | 8525 [5649, 11401]         | 9568 [4991, 14146]          | 76945 [71390, 82500]         | 184873 [135414, 234332]       |\n| **Fitted Order** | **0.37**                 | **1.0**                    | **1.0**                      | **1.0**                        |\n\n\n---\n**Appendix**\n\nFor Class ThetaEstimator, Class DelayImpactEstimator and data_splitting function, please refers to rebuttal for **Reviewer uxuX** Due to space constraints, additional codes and results are available upon request."}, {"review_id": "y1NiDsf2as", "reviewer": "Reviewer_iRrk", "summary": "This paper presents a novel approach to personalized ad bidding that simultaneously addresses delayed rewards, cumulative ad effects, and customer heterogeneity. The authors model this complex environment as a CMDP with delayed Poisson rewards, where context is used for personalization and states capture the history of ad exposure. A core contribution is the development of a two-stage maximum likelihood estimator (TS-MLE) combined with a data-splitting strategy, designed to efficiently and accurately estimate the delayed impacts of advertising. Based on this estimation framework, the paper proposes a reinforcement learning algorithm that learns personalized bidding strategies and is proven to achieve a near-optimal regret bound.", "questions": "1. The inner product often contains additional parenthesis and sometimes missing comma like in line 161", "limitations": "N/A", "rating": 3, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 2, "originality": 2, "strengths_and_weaknesses": "Strength\n1. The paper studied an important and interesting question in real-world ads bidding. All the three components have been extensively studied in the context of Ads CTR prediction task but not well studied under the auto bidding setting.\n2. The authors provide solid theoretical guarantees on the regret bound and proved that the proposed algorithm achieves near optimal regret.\n\nWeakness\n1. The proposed model is not realistic compared to real-world Ads applications. A fixed and simple linear structure is assumed to model cumulative effects while in CTR modeling sequence models are used. Moreover, the heterogeneity not only comes from user and context but also comes from different types of ads.\n2. The algorithm and the theoretical analysis relies on potentially strong assumptions that may be hard to generalize for example the state definition, highest competing bids follow a lognormal distribution, the specific reward function formula.\n3. The paper is entirely theoretical and lacks any experimental results to validate the proposed algorithms. Without experiments, even on synthetic data, it is difficult to assess the algorithm's practical performance, scalability, and robustness to assumption violations.", "was_revised": true, "final_justification": "I have read authors' rebuttal and will remain my initial evaluation", "rebuttal": "We sincerely appreciate the reviewer’s appreciation of our work, especially about its theoretical strength. We also appreciate the reviewer for pointing out some of the weaknesses of our work. We will address them one by one as follows and hope the reviewer will reconsider our rating.\n\n- We acknowledge that linear models may be overly simplistic for some real-world applications. However, more complex models, such as deep sequence models, often lack theoretical guarantees. To the best of our knowledge, our work is the first to provide a theoretical framework that jointly accounts for long-term effects, cumulative delayed impacts, and customer heterogeneity—three critical aspects that have not been addressed together in prior literature. Indeed, this point is also noted in your comment. Our current model can incorporate the ad effect. In particular, for the HOB modeling, we still just use $x_t$, since we do not know what types of ad the other bidders will show. But we can use a feature map say, $u_t=\\phi(x_t, ad_t)$, to model the demand, via $u^{\\top}_t \\theta$. The feature map can be as simple as $(x_t, ad_t)$ a concatenation. Extending our framework to move beyond linear structures is an important direction for future work. \n\n- Our state space modeling is highly flexible and can be easily extended to incorporate domain knowledge (see Appendix A.1 for details). We assume the highest competing bids follow a lognormal distribution, which is a standard choice in the literature. This assumption can be generalized to any flexible parametric distribution such as Gamma distribution. Regarding the reward structure, our formulation aligns with the common assumption in the literature that rewards are generated via a known linear feature mapping. Our model can also be seamlessly extended from a linear model to a GLM model, i.e. $\\psi(x^{\\top}_t \\theta)$, where $\\psi$ is a known link function such as logistic or exponential function.\n\n- Following your recommendation, we conducted a set of synthetic experiments that support two key points:\nOur algorithm empirically achieves near-optimal performance, with regret scaling as $\\sqrt{T}$, where $T$ is the number of customers.\nIt significantly outperforms several baseline policies, including an aggressive bidding strategy (which is close to the optimal strategy under our simulation setting), a passive bidding strategy, and a random bidding strategy.\n\n**Environment Setup**: We simulate a second-price auction with horizon $H = 3$ (a reasonable horizon length since in reality advertisers show their ads only a few times to each Internet user), context dimension $D = 2$, and $T = 20,000$ sequential customers. The first 2,400 rounds are for exploration; the rest for exploitation. Context vectors $x_t \\in \\mathbb{R}^2, d_l, \\beta_h, \\sigma_h$ are sampled elementwise from $|\\mathcal{N}(0,1)| + 0.1$, ensuring positivity. Parameters $\\theta_l  \\sim 5 \\cdot |\\mathcal{N}(0,1)| + 0.1$. Note that under our current simulation setting, an impression brings on average an instantaneous reward that is around 5 times than its cost (i.e. HOB price). Moreover, the reward of the impression decays quickly with time. These suggest that an aggressive bidding strategy (i.e. try to always win the bid and get the impression) is actually close to the optimal bidding strategy and thus serves as a competitive baseline policy.\n\n**Estimators**: We estimate four categories of parameters. $\\theta_l$ is learned using an online Newton method (Algorithm 3) with truncation threshold $\\tau = 100{,}000$, bound $B_\\theta = 10$, zero initialization, and $V_0 = I$. The delay impact $d_l$ is estimated via a two-stage MLE (Eq. 3) using $D_{t,l}$, $\\hat{\\theta}_l$, and $x_t$. $\\beta_h$ is estimated by ridge regression (Eq. 5, $\\lambda = 1.0$), and $\\sigma_h$ via empirical variance (Eq. 6). As $\\theta_l$ and $d_l$ are the most critical, we provide the corresponding code in the appendix.\n\n**Connection Between Bid Amount, Auction Outcome, and Realized Reward**: In our setting, the bidder's action is the bid amount, but due to the second-price auction format, the reward depends only on the outcome–whether the bid exceeds the highest other bid (HOB)-not the bid itself. Winning results in paying the HOB; losing incurs no cost. This decoupling allows optimal rewards to be computed from outcomes rather than bids.\nWe leverage this to evaluate both oracle and policy-based rewards. With full knowledge of true parameters, we enumerate all $2^H = 8$ possible win/loss outcomes across $H = 3$ rounds and define the **oracle reward** as the maximum achievable. With estimated parameters, we compute the expected reward for each outcome and choose the best sequence (Algorithm 1), which is then run through the simulator to obtain the realized reward. Regret is defined as the cumulative gap between oracle and actual rewards, reflecting errors from estimation and suboptimal bidding.\n\n**Simulation and Regret**\n1. Sample ground-truth parameters $(\\theta_l, d_l, \\beta_h, \\sigma_h)$, which remain fixed. Initialize estimates $(\\hat{\\theta}_l, \\hat{d}_l, \\hat{\\beta}_h, \\hat{\\sigma}_h)$ using default values (e.g., zeros or identity).\n2. Simulate $T = 20{,}000$ customers over two phases: exploration (first 2,400 rounds) and exploitation (remaining 17,600 rounds).\n3. Exploration Phase: Uniformly sample each of the $2^H = 8$ bidding outcome sequences across 2,400 rounds (300 per outcome). For each round: Sample context $x_t$; simulate reward and HOB under the chosen bidding outcome; Compute and record the oracle reward; Store observations for estimation; Apply data splitting to update parameter estimates.\n4. Exploitation Phase: For each round: Observe $x_t$; compute estimated rewards for all 8 bidding sequences using current estimates; Select the best sequence; simulate reward; compute oracle reward and reward gap; Update estimates via **data splitting**.\n5. Return cumulative regret as $np.cumsum(reward_{diff})$.\n\n**Baseline Policies**: We compare against three baselines. **Aggressive  bidding:** This simulates the strategy that the firm actively engages in winning ad impressions by consistently offering the highest bidding price (and pays second best price). In other words, the firm always wins by bidding above the HOB $(o_t = [1, 1, 1])$; **Bidding at random:** Sample $o_t$ uniformly from all 8 bidding outcomes and set bids accordingly; **Passive bidding:** This simulates the strategy that the firm rarely engages in the ad impression bidding war, where it gives very low bidding or simply does not bid $(o_t = [0, 0, 0])$.\n\nRegret for each is computed using the same oracle-based metric, serving as benchmarks for our algorithm.\nWe remark here again that due to our simulation setting, the aggressive bidding strategy is close to the optimal strategy. Therefore, it serves as a competitive benchmark, though it obviously suffers a O(T) regret since it is a fixed policy without any learning.\n\nWe run our proposed algorithm alongside the three baseline policies over 20 independent trials. The table below reports the average cumulative regret with ±0.5 standard deviation for all four algorithms. The last row shows the estimated regret order, obtained by applying a log-log transformation followed by linear regression. As shown, our algorithm achieves a fitted regret order of 0.37, while all three baselines exhibit linear regret. These results are consistent with our theoretical analysis and demonstrate the superior performance of our approach and the importance of learning.\n| Round   | Our Algorithm                 | Aggressive Bid              | Random Bid                   | Passive Bid                    |\n|---------|----------------------------|-----------------------------|------------------------------|-------------------------------|\n| 500     | 1770 [1174, 2379]          | 228 [121, 336]              | 1920 [1791, 2049]            | 4630 [3391, 5869]             |\n| 5000    | 8465 [5585, 11345]         | 2373 [1243, 3502]           | 19285 [17873, 20697]         | 46179 [33850, 58508]          |\n| 10000   | 8484 [5606, 11363]         | 4741 [2477, 7005]           | 38399 [35573, 41226]         | 92468 [67735, 117201]         |\n| 15000   | 8505 [5628, 11382]         | 7142 [3724, 10561]          | 57651 [53452, 61849]         | 138652 [101576, 175729]       |\n| 20000   | 8525 [5649, 11401]         | 9568 [4991, 14146]          | 76945 [71390, 82500]         | 184873 [135414, 234332]       |\n| **Fitted Order** | **0.37**                 | **1.0**                    | **1.0**                      | **1.0**                        |\n\n\n---\n**Appendix**\n\nFor Class ThetaEstimator, Class DelayImpactEstimator and data_splitting function, please refers to rebuttal for **Reviewer uxuX** Due to space constraints, additional codes and results are available upon request."}]

Author rebuttal:

Meta-review: The paper studies an online advertising setting focusing on three key factors: delayed and long-term effects, cumulative ad impacts such as reinforcement or fatigue, and customer heterogeneity. The authors formalize the problem as a specific instance of contextual MDPs and introduces an algorithm with strong theoretical guarantees. The algorithm is then validated on small-scale synthetic experiments.

After the initial round of reviews, the rebuttal, and the discussion, I'm proposing acceptance for the paper.

The paper is primarily theoretical in nature. Overall the technical contribution and the theoretical developments are borderline, as the results are technically sound, but there is no major surprising aspect in the analysis or in the algorithmic design. The other aspect that then enters into the decision is on whether the modeling part is significant and the paper is a rigorous study of how to design algorithms for the advertising scenario. On this aspect, the authors have made a significant effort in justifying most of the modeling choices and they are indeed pushing the boundary of previous theoretical models by considering different aspects of the problem that are significant in practice (the "delayed and long-term effects, cumulative ad impacts such as reinforcement or fatigue, and customer heterogeneity" mentioned in the abstract). As pointed out by several reviewers, there are indeed still residual assumptions that are not realistic (e.g., linear) and some elements that are not integrated yet (e.g., budget). On the former, I think it is important to discriminate between assumptions that are introduced to derive the theory or are intrinsic in the algorithm itself to the extent that we would not know how to use it beyond the theoretical assumptions. As discussed during the rebuttal, the authors have quite realistic ideas on how to extend the proposed algorithm to eg, using neural networks. On the second aspect (missing elements), I think the current submission is going in the right direction, although I would still encourage the authors to expand the discussion on the limitations of the current formalization and what are the next aspects of the real-world problem that would need to be studied to close the gap even further.

Finally, most reviewers were concerned with the scope of the empirical validation. Unfortunately there is no dataset or simulator commonly used to test online learning algorithms in these domains, so it's always very challenging to add any meaningful study, unless authors have direct access to production platforms. In this sense, what the authors reported in the rebuttal is probably the best that we can expect and I strongly encourage them to add it to the paper to provide a significant empirical validation of the setting and of the theoretical results.
Decision: Accept (poster)