Learning Personalized Ad Impact via Contextual Reinforcement Learning under Delayed Rewards

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.

• 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.

• 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.

• Following your recommendation, we conducted a set of synthetic experiments that support two key points: Our algorithm empirically achieves near-optimal performance, with regret scaling as $\sqrt{T}$, where $T$ is the number of customers. It 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.

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.

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.

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. We 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.

Simulation and Regret

1. 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).
2. Simulate $T = 20{,}000$ customers over two phases: exploration (first 2,400 rounds) and exploitation (remaining 17,600 rounds).
3. 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.
4. 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.
5. Return cumulative regret as $np.cumsum(reward_{diff})$.

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])$.

Regret for each is computed using the same oracle-based metric, serving as benchmarks for our algorithm. We 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.

We 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.

Appendix

For 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.

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.

Adding a Discussion of Related Work in “Learning-to-Bid”

We 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.

On recency bias and impact of state formulation

As 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.

We 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.

Experiments

As 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.

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.

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.

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. We 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.

Simulation and Regret

1. 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).
2. Simulate $T = 20{,}000$ customers over two phases: exploration (first 2,400 rounds) and exploitation (remaining 17,600 rounds).
3. 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.
4. 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.
5. Return cumulative regret as $np.cumsum(reward_{diff})$.

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])$.

Regret for each is computed using the same oracle-based metric, serving as benchmarks for our algorithm. We 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.

We 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.

Appendix

For 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.

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.

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.

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.

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. We 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.

Simulation and Regret

1. 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).
2. Simulate $T = 20{,}000$ customers over two phases: exploration (first 2,400 rounds) and exploitation (remaining 17,600 rounds).
3. 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.
4. 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.
5. Return cumulative regret as $np.cumsum(reward_{diff})$.

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])$.

Regret for each is computed using the same oracle-based metric, serving as benchmarks for our algorithm. We 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.

We 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.

Appendix

Due to space constraints, additional codes and results are available upon request.

def data_splitting(results):
    W_t_l = {}; D_t_l = {}
    for result in results:
         h = result['round']; s1 = result['S1']; s2 = result['S2'];o_t = result['o_t'];y = result['y_t']
         if o_t == 1:
            l = s1;W_t_l.setdefault(l, []).append((h, y))
         else:
            if s1 == 'inf':
               W_t_l.setdefault('-inf', []).append((h, y))  # For θ_{-inf}
            else:
               l = s1;D_t_l.setdefault(l, []).append((h, s2, y))
    return W_t_l, D_t_l
class ThetaEstimator:
    def truncate_payoff(self, y, x, V, tau):
        norm_x_V = np.sqrt(x.T @ V @ x); return y if norm_x_V * abs(y) < tau else 0.0
    def gradient_term(self, y, x, theta):
        return (-y + x @ theta) * x
    def constrained_quad_solver(self, theta0, V, k, b, tol=1e-6, max_iter=100):
        d = len(theta0)
        def phi(lambda_):
            A = V + 2 * lambda_ * np.eye(d); rhs = -k - 2 * lambda_ * theta0; return np.linalg.solve(A, rhs)
        def constraint(lambda_):
            phi_val = phi(lambda_); theta = theta0 + phi_val; return norm(theta) - b
        try:
            phi0 = np.linalg.solve(V, -k); theta_unconstrained = theta0 + phi0
            if norm(theta_unconstrained) <= b: return theta_unconstrained
        except: pass
        l, r = 0.0, 1e6
        for _ in range(max_iter):
            m = (l + r) / 2
            if constraint(m) > 0: l = m
            else: r = m
            if r - l < tol: break
        return theta0 + phi(r)
    def run_estimation_by_state(self, W_t_l, true_theta_l, X_t_l, theta_l_hat, V_l, tau=10, radius=1):
        error_l = {l: [] for l in W_t_l}
        for l, observations in W_t_l.items():
            for (round_idx, y_raw) in observations:
                x_t = X_t_l[l][round_idx]; y_t = self.truncate_payoff(y_raw, x_t, V_l[l], tau)
                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)
                V_l[l] += np.outer(x_t, x_t); theta_l_hat[l] = theta_next
                error = norm(theta_next - true_theta_l[l]) ** 2; error_l[l].append(error)
        return V_l, theta_l_hat, error_l
class DelayImpactEstimator:
    def __init__(self, d_true):
        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}; 
        self.d_hat = {l: [] for l in d_true}; self.errors = {l: [] for l in d_true}; 
        self.latest_d_hat = {l: np.nan for l in d_true}
    def run_update(self, D_t_l, x, theta_hat):
        self.theta_hat = theta_hat
        for l in D_t_l:
            for h, S2, y in D_t_l[l]:
                key = str(S2) if str(S2) in self.theta_hat else int(S2)
                theta = self.theta_hat[key]
                self.num[l] += y; self.denom[l] += np.dot(theta, x)
            d_hat = self.num[l] / self.denom[l] if self.denom[l] != 0 else np.nan
            self.d_hat[l].append(d_hat); self.latest_d_hat[l] = d_hat
            error = (d_hat - self.d_true[l]) ** 2 if not np.isnan(d_hat) else np.nan
            self.errors[l].append(error)
        return self.latest_d_hat

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.

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.

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.

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. We 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.

Simulation and Regret

1. 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).
2. Simulate $T = 20{,}000$ customers over two phases: exploration (first 2,400 rounds) and exploitation (remaining 17,600 rounds).
3. 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.
4. 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.
5. Return cumulative regret as $np.cumsum(reward_{diff})$.

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])$.

Regret for each is computed using the same oracle-based metric, serving as benchmarks for our algorithm. We 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.

We 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.

Appendix

Due to space constraints, additional codes and results are available upon request.

class ThetaEstimator:
    def truncate_payoff(self, y, x, V, tau):
        norm_x_V = np.sqrt(x.T @ V @ x); return y if norm_x_V * abs(y) < tau else 0.0
    def gradient_term(self, y, x, theta):
        return (-y + x @ theta) * x
    def constrained_quad_solver(self, theta0, V, k, b, tol=1e-6, max_iter=100):
        d = len(theta0)
        def phi(lambda_):
            A = V + 2 * lambda_ * np.eye(d); rhs = -k - 2 * lambda_ * theta0; return np.linalg.solve(A, rhs)
        def constraint(lambda_):
            phi_val = phi(lambda_); theta = theta0 + phi_val; return norm(theta) - b
        try:
            phi0 = np.linalg.solve(V, -k); theta_unconstrained = theta0 + phi0
            if norm(theta_unconstrained) <= b: return theta_unconstrained
        except: pass
        l, r = 0.0, 1e6
        for _ in range(max_iter):
            m = (l + r) / 2
            if constraint(m) > 0: l = m
            else: r = m
            if r - l < tol: break
        return theta0 + phi(r)
    def run_estimation_by_state(self, W_t_l, true_theta_l, X_t_l, theta_l_hat, V_l, tau=10, radius=1):
        error_l = {l: [] for l in W_t_l}
        for l, observations in W_t_l.items():
            for (round_idx, y_raw) in observations:
                x_t = X_t_l[l][round_idx]; y_t = self.truncate_payoff(y_raw, x_t, V_l[l], tau)
                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)
                V_l[l] += np.outer(x_t, x_t); theta_l_hat[l] = theta_next
                error = norm(theta_next - true_theta_l[l]) ** 2; error_l[l].append(error)
        return V_l, theta_l_hat, error_l
class DelayImpactEstimator:
    def __init__(self, d_true):
        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}; 
        self.d_hat = {l: [] for l in d_true}; self.errors = {l: [] for l in d_true}; 
        self.latest_d_hat = {l: np.nan for l in d_true}
    def run_update(self, D_t_l, x, theta_hat):
        self.theta_hat = theta_hat
        for l in D_t_l:
            for h, S2, y in D_t_l[l]:
                key = str(S2) if str(S2) in self.theta_hat else int(S2)
                theta = self.theta_hat[key]
                self.num[l] += y; self.denom[l] += np.dot(theta, x)
            d_hat = self.num[l] / self.denom[l] if self.denom[l] != 0 else np.nan
            self.d_hat[l].append(d_hat); self.latest_d_hat[l] = d_hat
            error = (d_hat - self.d_true[l]) ** 2 if not np.isnan(d_hat) else np.nan
            self.errors[l].append(error)
        return self.latest_d_hat

Thanks for your repsonse. However, I am sorry about some mislead in previous reivew. Let me make it clear: in Assumption 2.2, the conversion rate is assumed to be the form that is linear to the context. This is common in the field. for example contextual bandit, since it is helpful in proving concrete results. My concern is whether such a form is able to capture the conversion rate in real online ads platform, which leads to the necessarity of real-world empirical experiments.

We sincerely thank the AC for the discussion and we can incorporate neural-net as follows.

Just a brief recap of our model, if we win the bid, $o^t_h = 1$, the average product conversion rate $\mu^t_h = h_{S^t_{h, 1}}(x_t)$, where $x_t$ is the received feature of customer $t$, and $S^t_{h, 1}$ is the state which captures the time elapsed since most recent ads impression, $h_{S^t_{h, 1}}$ is the state dependent neural network which we want to estimate. If we lose the bid $o^t_h = 0$, the average product conversion rate $\mu^t_h = d_{S^t_{h,1}}h_{S^t_{h, 2}}(x_t)$, where $d_{S^t_{h,1}}$ is the delayed impact, and $S^t_{h, 2}$ is the time interval between the two most recent impressions (details see Def 2.1).

To incorporate the estimation of the state-dependent neural network $h_l$ (analogous to $\theta_l$) into our algorithm, we do the following. In essence, everything in Algorithm 1 remains unchanged, i.e. the exploration, exploitation, data-splitting strategy, and estimation, except the following modifications.

• First, we replace the estimation of $\theta_l$ (Eqn. (4)) by estimating the neural network $h_l$ by the following procedure (pertubed reward + gradient descent, similar to Algorithm 1 in [1])
  • We approximate $h(x)$ by $f(x, \theta) = \sqrt{m}W_L\phi(W_{L-1}\phi(\ldots \phi(W_1x)))$, where $m$ is the network width, and $\phi(x) = ReLU(x)$, $L$ is the neural network depth
  • We initialize $\theta_0 = (vec(W_1) \ldots vec(W_L))$ by random sample entry from N(0, 4/m) and do online updating by gradient descent with perturbed reward using observed product conversion $y^t_h$ by follows
    • Generated observation perturbation $\gamma_{s \in [t]}$ from Poisson $(\lambda)$, then generate binomial random variable $1_{s \in [t]}$ to add / subtract the noise from the observation
    • $\min_{\theta} L(\theta)$ = $\frac{1}{2} \sum^t_{s=1} (f(x_t, \theta) - (y^s_h + 1_{s} \gamma_s) )^2 + m \beta |\theta - \theta_0|^2$
  • Then based on this first stage estimates of $h$, plugging in to estimate delayed impact factor $d_l$ by $\frac{\sum^t_{s=1}\sum_{h \in D_{s, l}} y^s_h }{\sum^t_{s=1}\sum_{h \in D_{s, l}}f_{S^s_{h,2}}(x_s, \hat \theta)}$ (analogous to Eqn. (3))
• Since we do not have theoretical guarantees for $h$ estimation (no confidence interval), we cannot do UCB (Line 10 of our Algorithm 1). Instead, we might act greedily based on our point estimate. Even though Algorithm in [1] has theoretical guarantees, the key difference is that they assume noise of their observation is subGaussian, while in our case, it is not realistic to assume that the observation $y^t_h$ has sub-Gaussian noise, since product conversion has been known to have heavy tail for a long period of time. It is still a challenging open problem of developing theoretical-guaranteed neural contextual bandits with heavy tail observation.

Instead, our proposed framework leads to near-optimal results if we can parameterize $h_l(x_t) = \theta^{\top}_l \phi(x_t)$, where $\phi$ can be the neural net based embedding or other known feature mapping, then our algorithm remains near optimal, satisfying $\sqrt{T}$ regret bound in this case. This construction is very common in academia and industry as we mentioned from foundational studies such as [2] to the most recent ones [3]. During discussion with our industry friends over the rebuttal period, in the real-world, companies might construct these feature mapping using complicated methods but retain the overall linear structure for the ease 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_t$.

To summarize, our proposed framework leads to near-optimal results if there exists an online estimation oracle with theoretical guarantee for the estimation of $h$ and the estimation oracle employed in our paper based on our knowledge is SOTA. Our algorithm is possible to extend to a neural network if we drop the theoretical concerns. Developing theoretical guarantee for neural bandits under heavy tail observation is a promising future direction.

We hope our response clarifies the questions and we are open and willing to further discussions.

References:

[1] Learning Neural Contextual Bandits through Perturbed Rewards

[2] Provably Efficient Reinforcement Learning with Linear Function Approximation

[3] Nearly Optimal Algorithms for Contextual Dueling Bandits from Adversarial Feedback