{"id":"97edef7c-b9ff-47a5-8ee8-70b1aa51d938","arxiv_id":"2502.02920","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":5.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":8,"one_line_summary":"A combinatorial bandit with saturating mean, efficiency-weighted targeted exploration, and change-point detection improves simulated multichannel ad budget allocation compared with UCB, Thompson sampling, and sliding-window baselines.","lead":"This paper builds a simulator that mimics months-long multichannel ad campaigns and proposes a combinatorial bandit algorithm that adjusts daily budgets across sub-campaigns, using a saturating reward model, targeted exploration, and change-point detection. The authors report higher clicks, lower regret, and lower cost per click than several bandit baselines in their simulated campaigns.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"The O(sqrt T) regret theorem is not proven: the union bound in §8.2 diverges for any k_j<1, invalidating the high-probability event before the targeted-exploration argument.","rationale":"The paper's central claim is twofold: a theoretical O(sqrt T) sublinear regret bound and empirical superiority in a simulator fitted to logged data. For the theory to hold, the proof in §6 and Appendix 8.2 must establish a valid high-probability event and then bound regret via information gain. The most insecure condition is the union bound: the chosen β_{j,t} depends on k_j=(1−θ_j), and whenever θ_j>0 the exponent 2k_j<2 makes the series ∑ t^{−2k_j} diverge. This is a concrete mathematical error that invalidates the theorem even in the simplest stationary case. The reader's identified weakness (Assumption 3) is also real: monotone per-arm rewards do not justify excluding lower budget levels from exploration because the global budget cap can make low budgets part of the optimal super-arm, and uncertainty there matters. However, that argument only affects the regret-reduction component of the theorem; the base regret bound is already unproven due to the union-bound failure. The empirical section is promising but the abstract's 'real-world campaigns' overstates the fitted-simulator evaluation. The verdict remains CONDITIONAL because the paper is repairable: correct the proof or soften the theoretical claim, clarify the simulation-based nature of the experiments, and provide code/data artifacts. Thus no change from the reader's conditional verdict is needed, though the stated reason should be sharpened to include the union-bound error.","tokens_in":17448,"tokens_out":8351,"duration_ms":77138,"concrete_test":"Recompute the union-bound sum in §8.2 with k_j=0.5 (θ_j=0.5), M=500, N=3, δ=0.05. The term is M(3δ/(π^2 N M t^2))^{0.5} ≈ 500 × 3.18×10^{-3} × t^{-1} ≈ 1.59/t. Summing to T=10^4 gives ≈1.59×ln(10^4)≈14.6, which is far above δ/2=0.025. More generally, show that for any k_j<1, ∑_{t=1}^T t^{-2k_j} diverges as T→∞, so the claimed probability bound cannot hold for all T. If this check confirms the divergence, Proposition 6.2's proof is invalid as written. The authors would need either a different exploration-dependent β schedule that preserves a convergent series (e.g., k_j=1) or a revised theorem.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The main regret bound (Prop. 6.2/8.2) rests on an invalid union bound. With β_{j,t}=2k_j log(π^2 N M t^2/(3δ)), k_j=(1−θ_j)∈(0,1], the proof asserts ∑_{t=1}^T ∑_{j=1}^N M e^{−β_{j,t}/2} ≤ δ/2. However e^{−β_{j,t}/2} = (3δ/(π^2 N M t^2))^{k_j}, so the t-series behaves as ∑ t^{−2k_j}. For every k_j<1 (i.e., any campaign with positive normalized CPC, θ_j>0), the series diverges as T→∞; even for finite T the partial sum grows like T^{1−2k_j} (or log T if 2k_j=1), not O(1). The union bound therefore fails, and the high-probability event used to replace true rewards by GP upper confidence bounds is not guaranteed. Consequently the derivation of R_T(𝑈)=O(√(T∑γ_T)) — the paper's central theoretical contribution — is unsupported, independent of the Assumption 3 monotonicity argument for the targeted exploration. The claim that 'regret is reduced by restricting exploration to b> b_j,max' is secondary: even if γ_T(𝑈+, X+_j)≤γ_T(𝑈) held, the base bound it modifies is not established. This is a load-bearing gap, not a stylistic issue.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper proposes TUCB-MAE, a combinatorial bandit algorithm for multichannel advertising budget allocation under a total daily budget cap. The algorithm combines a Gaussian-process reward model with a saturating mean, a target-UCB exploration rule that only explores budget levels above the current best level, and change-point detection for non-stationary rewards. The authors also build a simulation environment calibrated to logged ad-campaign data and report experiments on several campaign groups. The paper claims a sublinear regret bound of O(√T) and lower regret than standard exploration techniques, plus empirical improvements over UCB, Thompson sampling, sliding-window, and discounted-reward baselines.","tokens_in":17876,"tokens_out":7518,"duration_ms":64800,"significance":"The practical contribution is real: the paper ships a publicly available simulator driven by logged campaign data, evaluates on multiple campaign types, and includes an ablation study showing the contribution of each algorithmic component. The empirical comparisons are internally consistent and the design of a non-stationary, combinatorial-bandit budget allocator with change-point detection is a useful engineering contribution. If the theoretical guarantees were valid, the method would also be of theoretical interest. However, the paper's headline theoretical claim — sublinear regret with a reduced bound from targeted exploration — is not established. The proof contains a concrete mathematical error in the union bound, and the regret-reduction argument is not a derivation. These flaws undermine the central theoretical contribution, which the paper explicitly touts as one of its three main contributions.","major_comments":[{"comment":"The union bound used to construct the high-probability event is invalid. With β_{j,t} = 2k_j log(π²NMt²/(3δ)) and k_j = (1-θ_j) ∈ (0,1], the bound becomes Σ_{t=1}^T Σ_{j=1}^N M e^{-β_{j,t}/2} = Σ_{j=1}^N M (3δ/(π²NM))^{k_j} Σ_{t=1}^T t^{-2k_j}. The series Σ t^{-2k_j} diverges for k_j ≤ 1/2 (in particular for campaigns with normalized CPC θ_j ≥ 1/2), and even for 1/2 < k_j < 1 it is not bounded by the claimed (6/π²)Σ 1/t² with the same constants. Since k_j is not restricted to values ≥ 1/2, the series cannot be uniformly bounded by δ/2, and the event that all GP upper-confidence bounds hold does not hold with probability 1−δ. The subsequent inequality R_T(U) ≤ ... therefore does not follow.","section":"§8.2 (Appendix), union-bound step"},{"comment":"The claimed reduction R_T(U+) ≤ R_T(U) from restricting exploration to X+_j is not derived. The inequality γ_T(n_j, X+_j) ≤ γ_T(n_j) is a trivial property of information gain on a subset; it holds for any subset and does not by itself bound regret. A regret bound for the restricted algorithm requires that the optimal super-arm lie in the restricted action set, or a quantified cost for excluding it. Under the total budget constraint (1b), the optimal allocation can assign a sub-campaign a budget below its current b_{j,max}; Assumption 3 (monotone, concave per-campaign rewards) does not prevent such lower budgets from being part of the optimal super-arm. Excluding them from exploration can therefore cause linear regret, so the claimed reduction is unsupported and potentially false.","section":"§6, Proposition 6.2 and §8.2"},{"comment":"The proof conflates the true reward function n_j with the GP estimate ˆn_j. Assumption 3 imposes monotonicity and concavity on n_j, but the regret analysis in Lemma 6.1 applies to the GP posterior on ˆn_j; the GP estimate with a saturating mean is not shown to be monotone. Moreover, b_{j,max} is defined in the algorithm as the budget level with highest predicted reward, but the proof does not define how this quantity is updated over time nor why it is a valid surrogate for the minimizer of the information-gain regret bound. A rigorous proof would need to couple the evolution of b_{j,max} with the exploration decisions; none is given.","section":"§6, Eq. (6)-(7) and §8.2"}],"minor_comments":[{"comment":"The simulator models the reward as a power law n_j(x) = α_c x^{ω_c} + ε with parameters fitted to logged data, and the cost is drawn from a truncated normal. The paper's phrase \"multiple real-world campaigns\" should be clarified: the campaign data are logged, but the rewards are synthesized through this fitted power-law model rather than observed from real platform feedback.","section":"§5, Simulation Environment"},{"comment":"The proof refers to \"Lemma 5.6 of [35]\" in the main text (Section 6) but to \"Lemma 5.3 in [35]\" in the Appendix; the reference number should be made consistent.","section":"§8.2, reference numbering"},{"comment":"The symbol M is used both as the number of possible budget combinations (Table 3) and as the per-campaign action-set size in the union-bound sum (\"for each action a∈D\"). This ambiguity affects the readability of the proof; the authors should distinguish the cardinality of the per-campaign action set from the number of super-arms.","section":"§8.2 and Table 3, notation M"},{"comment":"The text notes that the algorithm is unable to adapt to a very short non-stationary change around day 250. This is a real limitation and should be discussed in the conclusion rather than as a one-line remark, since it bears on the method's practical robustness.","section":"§7, Figure 5 discussion"},{"comment":"In the Criteo experiment the proposed method is compared only to UCBGP and TSGP without change-point detection; the absence of non-stationarity in this dataset means the comparison tests only the targeted-UCB and saturating-mean components. The caption should state this scope explicitly.","section":"§7.3, Table 2"}],"recommendation":"reject","confidential_remarks":"The paper's empirical work is potentially publishable as an application or systems contribution, but the central theoretical claim is a headline contribution and it is mathematically invalid: the union bound diverges for a range of k_j, and the targeted-exploration regret-reduction argument is not a proof. The flaws are load-bearing because they concern the paper's main advertised result. In my view, a revision would need either to remove the regret-reduction claim and provide a correct sublinear-regret analysis for the actual algorithm (which may require additional assumptions on the action set), or to reframe the contribution as strictly empirical. As written, the paper does not meet the bar for acceptance."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"The paper is worth a look for the simulator and the engineering of TUCB-MAE, but the central theoretical claim—sublinear regret, moreover reduced by targeted exploration—is not supported by the proof as written.\n\nWhat's genuinely new: a public simulation environment that fits power-law reward models to logged multichannel ad campaigns with cost variability and change points; a saturating mean that fixes the zero-mean GP prior; and CPC-weighted targeted exploration that only explores budget levels above the current best. These are sensible, practically motivated modifications to the ABA/GP-UCB line, and the ablation study suggests each piece helps in their simulator. Experiments across several platform A/B campaign groups show consistent gains over standard UCB, sliding-window, discounted, and TS baselines.\n\nThe soft spot is the theory. The proof of Proposition 6.2/8.2 uses a union bound that does not hold. With β_{j,t}=2k_j log(π^2NMt^2/(3δ)), the term M e^{-β/2} behaves like (3δ/(π^2NMt^2))^{k_j}, so summing over t gives a series in t^{-2k_j}. The proof bounds this by the Basel sum π^2/6, which is only valid if k_j≥1, contradicting k_j∈(0,1]. For k_j<1 the sum is larger; for k_j≤1/2 it diverges. So the high-probability event used to replace true rewards by GP upper bounds is not guaranteed with the stated δ, and the O(√T) regret bound is unsupported. (To be fair, the stress-test note overstates that \"any k_j<1\" causes divergence—series converge for k_j>1/2—but the bound used is still invalid.)\n\nThe separate claim that targeted exploration reduces regret, γ_T(ẑ_j, X_+j) ≤ γ_T(ẑ_j), is true in the trivial information-theoretic sense but does not do the work they need. The regret bound depends on the exploration policy's information gain on the actual chosen actions; restricting the action set changes the kernel and the posterior, and the monotonicity argument (Assumption 3) doesn't guarantee that low-budget arms are never part of the optimal super-arm under a total budget cap.\n\nOverall: the engineering contribution is real, the empirical story is promising, and the simulator is a valuable resource. But the theoretical claims should be heavily conditioned or fixed before publication. The paper deserves a serious referee because the problem matters and the artifacts are reusable, but I'd advise not to rely on the regret bound.","headline":"Useful simulator and sensible algorithm, but the regret bound is not proven and the paper overstates its theoretical contribution.","tokens_in":18337,"tokens_out":4188,"would_cite":false,"duration_ms":33771,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"deepseek-v4-flash","headline":"TUCB-MAE, a combinatorial bandit for ad-budget allocation, claims sublinear regret and beats UCB, Thompson, sliding-window, and discounting baselines on real campaigns.","keywords":["combinatorial bandit","budget allocation","non-stationarity","Gaussian process regression","change point detection","digital advertising","multi-choice knapsack","upper confidence bound"],"falsifier":"Fit GP reward curves from the released simulator and look for any sub-campaign whose estimated mean reward is not monotone over the allowed budget range; if one exists, run TUCB-MAE with and without the targeted-exploration restriction. The claim fails if the restricted version's cumulative regret exceeds the unrestricted version or if a higher-budget allocation is chosen while a lower budget would have earned more clicks.","tokens_in":17272,"feed_emoji":"💰","tokens_out":9969,"duration_ms":102244,"temperature":0.7,"pith_summary":"Advertisers who split one daily budget across many channels face a moving target: each channel's reward curve shifts over time, and exploring every budget level is expensive. This paper sets out to show that a combinatorial bandit can handle both problems at once. Its algorithm, TUCB-MAE, models each sub-campaign's budget-to-reward curve with a Gaussian process, caps the predicted curve at the current best budget level, and only explores budgets above that level; a change-point detector refreshes the model when the market shifts. The authors prove sublinear regret of order $O(\\sqrt{T})$ and report that, on logged multichannel campaigns, the method obtains more clicks with lower cost per click than UCB, Thompson sampling, sliding-window, and discounted-reward baselines. If the claims hold, the work turns a proprietary-data problem into a reproducible benchmark problem with a practical allocation policy.","feed_headline":"Bandit ad-spend allocator cuts regret by skipping low-value budgets","feed_subtitle":"On logged campaigns it beats UCB, Thompson, sliding-window, and discounting baselines in clicks and cost per click.","key_machinery":"The two main mechanisms are the saturating mean and the targeted exploration indicator. For a sub-campaign $j$ with discrete budget levels $B$, the GP mean is modified so that $\\hat n_j(b) = \\hat n_{j,\\max}$ for every $b > b_{j,\\max}$, where $b_{j,\\max}$ is the budget level with the highest predicted reward so far; this encodes the domain knowledge that more spend yields more reward but with diminishing returns. The exploration bonus $\\beta(1-\\theta_j)\\sigma_j$ is multiplied by the indicator $\\mathbb{I}[b_{j,i} > b_{j,\\max}]$, so uncertainty is resolved only where a better optimum might appear, with more efficient arms (lower cost per click) explored more aggressively. Around these, the algorithm wraps a Gaussian process regressor over each arm, a multi-choice knapsack dynamic program to solve the daily allocation under the total budget cap, and a mean-average-error test between the long-term model and a short sliding-window model to detect breakpoints. The information gain $\\gamma_T(\\hat n_j)$ is the quantity that carries the regret bound, and the design shrinks it by shrinking the explored arm space to $X_j^+$.","core_discovery":"The paper's central claim is that the combination of a saturating mean function, a target-region exploration utility, and MAE-based change-point detection (the TUCB-MAE algorithm) improves both the theory and the practice of multichannel budget allocation. The saturating mean replaces a zero-mean GP prior with one that clamps predictions at the highest reward observed so far for each sub-campaign, removing the pessimistic low predictions at high budgets. The exploration utility adds $\\beta(1-\\theta_j)\\sigma_j$ to the GP upper confidence bound only for budget levels above the current best level $b_{j,\\max}$, where $\\theta_j$ is a normalized efficiency measure such as cost per click; this is justified by Assumption 3 that reward functions are monotone increasing and concave. In the GP-UCB regret framework, restricting exploration to the space $X_j^+$ of higher budgets gives $\\gamma_T(\\hat n_j, X_j^+) \\le \\gamma_T(\\hat n_j)$, so the regret bound $R_T(U^+) = \\tilde O(\\sqrt{T N \\sum_j \\gamma_T(\\hat n_j, X_j^+)})$ is no larger than the standard bound and the paper reports better empirical performance than all five baselines across four campaign groups from two platforms.","pith_inferences":["An extension the authors leave implicit: the targeted-exploration indicator could be applied symmetrically when a reward curve has an interior peak, which would let the algorithm detect violations of monotonicity instead of assuming them away.","The efficiency weight $\\theta_j$ is normalized cost per click; using conversion value instead would likely sharpen the pseudo-conversion results reported in Section 7.1.","The change-point detector assumes abrupt shifts separated by at least $T_p$ days; gradual drift or seasonal cycles would need a different detector, and the paper's theory does not cover those cases."],"forward_implications":["Under the monotone-concavity assumption, exploration below the current best budget is provably wasted, so the targeted indicator makes the algorithm safe as well as efficient.","The $O(\\sqrt{T})$ regret bound means the cost of learning the allocation policy grows sublinearly, so longer campaigns amortize the exploration cost.","The empirical results indicate the method can be used in place of standard UCB, Thompson sampling, sliding-window, and discounted-reward policies in deployed campaigns.","The released simulation environment lets subsequent work compare allocation policies on the same non-stationary logged data rather than on synthetic curves."],"supporting_citations":[{"why":"Supplies the GP-UCB regret-analysis lemmas and information-gain bounds used to prove the sublinear regret result.","marker":"[35]"},{"why":"Formulates the automatic budget allocation (ABA) problem as a combinatorial bandit and provides the baseline framework the paper extends.","marker":"[27]"},{"why":"Provides the zero-mean Gaussian process model of budget-to-reward that the saturating mean modifies.","marker":"[28]"},{"why":"Models cost-to-reward as a power law and motivates Assumption 3's monotone concave reward functions.","marker":"[19]"},{"why":"Uses parametric reward models with Thompson sampling for performance marketing, a comparison point for the proposed exploration utility.","marker":"[17]"},{"why":"Provides the open Criteo attribution dataset used to test the method in a stationary setting.","marker":"[12]"},{"why":"Defines the sliding-window and discounted UCB baselines that the experiments compare against.","marker":"[15]"},{"why":"Provides the sliding-window Thompson sampling baseline used in the empirical comparison.","marker":"[14]"},{"why":"Defines the multiple-choice knapsack solver used to allocate budgets under the total budget cap.","marker":"[22]"}],"fun_headline_variants":["Saturating-mean bandit adapts ad budgets to market shifts","Change-point detection sharpens combinatorial bandit for ads","Targeted exploration in bandits cuts ad spend regret","Adaptive budget allocator beats five baselines on real campaigns","Combinatorial bandit with change-point detection lowers ad regret"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"Everything rests on the assumption that every sub-campaign's reward function is monotone increasing and concave in spend; if a lower budget can ever beat the current best, skipping exploration there can miss the optimum and the claimed regret reduction stops being valid.","fun_headline_variants_meta":{"raw":{"variants":["Saturating-mean bandit adapts ad budgets to market shifts","Change-point detection sharpens combinatorial bandit for ads","Targeted exploration in bandits cuts ad spend regret","Adaptive budget allocator beats five baselines on real campaigns","Combinatorial bandit with change-point detection lowers ad regret"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000403,"raw_usage":{"total_tokens":2129,"prompt_tokens":1004,"completion_tokens":1125,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":620,"completion_tokens_details":{"reasoning_tokens":1041}},"tokens_in":620,"tokens_out":1125,"duration_ms":62762,"temperature":1.0,"reasoning_tokens":1041,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-09T10:36:45.283135+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Fit GP reward curves from the released simulator and look for any sub-campaign whose estimated mean reward is not monotone over the allowed budget range; if one exists, run TUCB-MAE with and without the targeted-exploration restriction. The claim fails if the restricted version's cumulative regret exceeds the unrestricted version or if a higher-budget allocation is chosen while a lower budget would have earned more clicks.","supporting_citations":[{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Supplies the GP-UCB regret-analysis lemmas and information-gain bounds used to prove the sublinear regret result."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Formulates the automatic budget allocation (ABA) problem as a combinatorial bandit and provides the baseline framework the paper extends."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Provides the zero-mean Gaussian process model of budget-to-reward that the saturating mean modifies."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Uses parametric reward models with Thompson sampling for performance marketing, a comparison point for the proposed exploration utility."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Provides the open Criteo attribution dataset used to test the method in a stationary setting."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Defines the sliding-window and discounted UCB baselines that the experiments compare against."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Defines the multiple-choice knapsack solver used to allocate budgets under the total budget cap."}],"review_version":1}