{"id":"cb1afe9b-ce08-4b03-8cec-8ee8434bea75","arxiv_id":"2607.13546","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":5.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":3,"one_line_summary":"A cost-aware bandit algorithm that learns improving-then-saturating worker quality and unknown costs achieves O(log B) regret for budgeted crowdsensing worker recruitment.","lead":"This paper designs an online learning algorithm for mobile crowdsensing platforms that must recruit smartphone users whose sensing quality improves with experience before leveling off. The algorithm learns each worker's learning curve and cost in real time, and the authors prove its losses stay logarithmic in the size of the budget.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Theorem 1's N0 is 256× too small; the proof's key ε-smallness step fails as written, so O(log B) is not established.","rationale":"The reader's weakest_assumption identified two issues: the unverified import from [28] under resets, and the factor-256 shortfall in N0. I agree with the N0 shortfall and treat it as the primary load-bearing concern because it is internal, elementary, and directly breaks the main concentration step in the proof of Theorem 1. The logarithmic regret claim may still be true after a constant correction, so this does not warrant rejection; it does mean the theoretical guarantee is not established as written. On the [28] issue, I am less certain: the borrowed propositions may or may not degrade under the reset/refit loop, but the manuscript provides no argument either way, so it remains a secondary risk. Overall the appropriate verdict remains CONDITIONAL, matching the reader's judgment, since the paper's central claim is plausible but the current proof contains a concrete, fixable numerical gap plus an unverified dependency on external results.","tokens_in":21038,"tokens_out":14598,"duration_ms":161201,"concrete_test":"Take a concrete instance, e.g. K=2, c_i=0.5, μ*_i=0.8, Δ_i=0.1, B=10^6, and compute the two required thresholds using ε_{i,t}=16√(2 ln B/N). Check whether the N0 defined in Theorem 1 satisfies both 2ε ≤ 0.5 c_i and ε ≤ Δ_i c_i^2/(8(μ*_i+c_i)). Direct algebra shows it fails by a factor of 256. Then verify that replacing N0 by 256·N0 restores both inequalities; if so, the logarithmic-order claim survives but with a corrected constant, and the theorem statement and proof must be amended accordingly.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The proof of Theorem 1 relies on the claim that N_{i,t} ≥ N0 ensures both 2ε_{i,t} ≤ 0.5c_i and ε_{i,t} ≤ Δ_i(c_i)^2/(8(μ*_i+c_i)). With the paper's own definition ε_{i,t}=16√(2 ln B / N_{i,t}) (set δ=1/B in the proof), the first condition requires N ≥ 8192 ln B / c_i^2. The N0 defined in the theorem is at most 32 ln B / c_i^2 when min{·,·}=c_i/4. The second condition requires N ≥ 32768 ln B (μ*_i+c_i)^2/(Δ_i^2 c_i^4), while the defined N0 gives at most 128 ln B (μ*_i+c_i)^2/(Δ_i^2 c_i^4) when the minimum is the Δ-term. In both cases N0 is 16^2 = 256 times too small. Therefore the displayed inequality labeled (c) — the step that bounds P(E_t^2) by 2/B^2 — is not implied by N0 as stated. This is an internal, checkable gap in the central logarithmic-regret argument, independent of whether the imported propositions from [28] hold under the algorithm's resets. The latter issue is also real: Eq. (4) and Proposition 1 are invoked inside a loop that resets N_{i,t} to 1 and refits the linear model on plateau data, and no proof is given that the [28] concentration and change-detection inequalities remain valid under these resets. But the N0 mismatch alone already invalidates the proof as written.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies a budget-constrained sequential worker recruitment problem in mobile crowdsensing. Each worker's expected reward is modeled as an unknown increasing-then-converging function of the number of assigned tasks, and each worker has an unknown expected cost. The authors formulate the problem as a structured bandit, prove in Lemma 1 that the offline optimum is rho* B + O(1) where rho* is the maximum converged reward-to-cost ratio, and propose CATI-UCB, which combines a piecewise-linear reward model, a cost-aware optimistic selection rule, and change-point detection to reset learning after saturation. They claim an O(log B) regret bound in Theorem 1 and support the method with extensive synthetic and trace-driven experiments. The main theoretical result, however, is not established as written due to specific gaps in the proof of Theorem 1.","tokens_in":21586,"tokens_out":17778,"duration_ms":163715,"significance":"If the logarithmic regret bound is established, the paper makes a useful contribution: it extends time-increasing bandits to a budget-constrained setting with unknown costs, and the offline characterization in Lemma 1 is a clean and correct simplification that justifies focusing on the highest converged reward-to-cost ratio. The algorithmic design is well motivated, and the experimental study is unusually broad for a theory paper, covering piecewise-linear and negative-exponential reward dynamics, 12-worker settings, heterogeneous task types, hyperparameter sensitivity, and trace-driven data based on Topcoder. I also credit the authors for giving a self-contained offline-optimality lemma rather than only an asymptotic statement. However, the proof of Theorem 1 contains concrete, checkable gaps: the stated N0 is too small by a factor of 256, one of the key probability bounds uses the wrong tails, and the imported guarantees from [28] are used without verifying their validity under the algorithm's reset mechanism. These issues are local and likely fixable while preserving the O(log B) claim, but they block acceptance in the current form.","major_comments":[{"comment":"The proof asserts that N_{i,t} >= N0 ensures both 2 eps_{i,t} <= 0.5 c_i and eps_{i,t} <= Delta_i (c_i)^2 / [8(mu*_i + c_i)], where eps_{i,t} = 16 sqrt(2 ln B / N_{i,t}). Solving these inequalities gives N_{i,t} >= 8192 ln B / c_i^2 and N_{i,t} >= 32768 ln B (mu*_i+c_i)^2 / (Delta_i^2 c_i^4), respectively. The stated N0 = 2 ln B / min^2{ Delta_i c_i^2/[8(mu*_i+c_i)], c_i/4 } is at most 32 ln B / c_i^2 in the first case and at most 128 ln B (mu*_i+c_i)^2/(Delta_i^2 c_i^4) in the second case. In both cases N0 is 256 times too small to imply the two displayed inequalities. Consequently, the inequality labeled (c) in the proof does not follow, and the bound P(E2_t) <= 2/B^2 is not established. The theorem's conclusion can likely be repaired by enlarging N0, but the proof as written is invalid.","section":"Theorem 1 proof, step (c)"},{"comment":"The proof bounds P(E1_t) by 2/B^2 using the statements P(hat mu_{i^dagger} > mu*_{i^dagger} | ...) >= 1 - 1/B^2 and P(hat c_{i^dagger} < c_{i^dagger} | ...) >= 1 - 1/B^2. These are the wrong tails for E1_t: E1_t is the event that the optimistic ratio is below the true ratio by Delta_i/2, whereas upper bounds on the reward estimator and lower bounds on the cost estimator make the ratio larger, not smaller. Bounding E1_t would require a lower tail for the reward estimator and an upper tail for the cost estimator, neither of which is supplied by Eq. (4) or the cited Proposition 1. Without a valid bound on P(E1_t), the decomposition of E[N_{i,T}] into E1_t/E2_t does not yield the advertised number of suboptimal pulls.","section":"Theorem 1 proof, event E1_t"},{"comment":"The concentration bound in Eq. (4) and the change-detection guarantee in Proposition 1 are imported from [28]. Algorithm 1, however, resets N_{i,t} to 1 on every detected saturation and refits the linear model on the post-change plateau segment. No argument is given that the imported inequalities remain valid under these resets. The citation itself is inconsistent: Eq. (4) refers to \"Proposition 1 of [28]\", while the displayed Proposition 1 is labeled \"Proposition 2 of [28]\". Because Lemma 3 and the proof of Theorem 1 rely on these imported guarantees, the applicability under the algorithm's reset mechanism is load-bearing and must be explicitly established.","section":"Section 4.2 and Theorem 1"},{"comment":"N_{i,t} is defined in Section 3 as the cumulative number of times worker i has been selected, equal to sum_{s=1}^t 1{A_s = i}. Algorithm 1 line 11, however, sets N_{A_t,t} = 1 upon change-point detection, making N_{i,t} a local post-reset count. The regret proof mixes the two interpretations: quantities such as N_{i,T_{C,B}} and tau_i are cumulative, while confidence radii and the event N_{i,t} >= N0 + tau_i appear to use the local count. This notational collision makes the event definitions in the proof of Theorem 1 ill-posed. The authors should introduce separate notation (e.g., m_i(t) for the segment-local count and n_i(t) for the cumulative count) and rewrite the affected arguments.","section":"Section 3 vs. Algorithm 1"},{"comment":"Section 4.2.2 defines hat mu_{i,t} = bar mu_{i,t} + eps_{i,t} and hat c_{i,t} = bar c_{i,t} - eps_{i,t}, and states that the algorithm selects the worker maximizing hat mu_{i,t} / hat c_{i,t}. Algorithm 1 line 5 instead selects arg max_i (hat mu_{i,t} + eps_{i,t}) / max(hat c_{i,t} - eps_{i,t}, 0.001), which adds eps a second time in the numerator and subtracts it a second time in the denominator. The regret proof analyzes the once-padded ratio. The algorithm, Eq. (4), and the proof must be reconciled; otherwise the theoretical guarantee is for a different selection rule than the one implemented.","section":"Algorithm 1, line 5 vs. Section 4.2.2"}],"minor_comments":[{"comment":"The summation in the last term is written as sum_{i in [N]} but the worker set is [K]; this appears to be a typo.","section":"Lemma 2"},{"comment":"The constant N0 depends on i through Delta_i, c_i, and mu*_i but is written without an index. It should be N0^{(i)} or defined per worker to avoid confusion.","section":"Theorem 1"},{"comment":"The line P(F_i D_i) = P(v_i < tau_1 < v_i + omega) has a typo: it should be tau_i. In addition, the threshold used in Algorithm 1 line 10 is not the same as the gamma defined in Lemma 3; please reconcile the constants.","section":"Lemma 3"},{"comment":"The constant 0.001 in the denominator of line 5 is never defined in the text; the proof later refers to it as eta. Define eta and state any assumption relating it to c_min.","section":"Section 4.2.2 / Algorithm 1"},{"comment":"The trace-driven experiments are said to be shown in \"Fig. 7(a)\" and \"Fig. 7(b)\", but the actual trace-driven figures are Fig. 10(a) and Fig. 10(b). The cross-references should be fixed.","section":"Section 6.6"},{"comment":"The notation for the expected reward of a worker on a given pull alternates between mu_{i,s} in Eq. (2) and mu_i(l) in the proof of Lemma 2. Use one consistent notation.","section":"Eq. (2) and Lemma 2"}],"recommendation":"major_revision","confidential_remarks":"The core obstacle is the proof of Theorem 1, not the problem formulation or the experiments. The N0 mismatch and the wrong-tailed E1_t argument are concrete and easily verifiable; both can be repaired without changing the algorithmic idea, but the proof needs a complete rewrite. The deeper concern is the heavy reliance on imported results from [28] under an algorithm that resets local counts and refits models on plateau data. I would ask the editor to require the authors to either prove the needed concentration and change-detection statements under their reset mechanism or clearly state the conditions under which the imported results apply. The experimental study is a strength and suggests the method is effective, but the theory must be correct before publication."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"The problem you'd care about here is real: budget-constrained bandits where each arm's reward increases then plateaus, and costs are unknown. The paper gives a clean offline characterization (Lemma 1) showing that spending the whole budget on the worker with the highest converged reward-to-cost ratio is optimal up to an additive constant. That is a useful anchor. CATI-UCB is a natural extension of TI-UCB with a cost-aware selection rule, and the regret decomposition in Lemma 2 is a nice reduction.\n\nThe central proof, however, has a concrete gap. In Theorem 1, N0 is defined as 2 log B / min^2{...}. With ε = 16 sqrt(2 ln B / N), the step at inequality (c) needs 2ε ≤ 0.5c_i and ε ≤ Δ_i c_i^2 / (8(μ*+c_i)). Working through the constants, N0 is 256× too small to imply either inequality. So the displayed derivation does not go through, and the O(log B) regret bound is not established with the stated N0. The good news: enlarging N0 by a constant factor still yields O(log B), so the theorem is likely repairable. But as written, the proof has a real flaw.\n\nA second, more serious concern is the reliance on Propositions 1 and 2 from [28]. The proof invokes those concentration and change-detection guarantees inside a loop where the algorithm resets N_{i,t} to 1 after every detected saturation and refits the linear model on plateau data. No argument is given that the external propositions remain valid under such resets. This is not a constant-level issue; it is an unverified assumption about the imported machinery. If those propositions require a continuously increasing trend and no resets, the proof collapses. The authors need to show the conditions for [28]'s results are satisfied in this setting, or supply their own proofs.\n\nThe experiments are okay but thin: 20 runs, no error bars, and the 'real-world' trace is reconstructed from published curves rather than raw data. Hyperparameter sensitivity is a nice addition.\n\nWho is this for? Researchers in bandits with budgets, non-stationary bandits, and crowdsourcing. It is a competent extension with a genuinely new problem formulation and a plausible algorithm, but the theory needs repair. I would send it to a serious referee, not desk reject, and the referee should focus on the N0 constant and the [28] imports. If those are fixed, this becomes a solid contribution.","headline":"New problem formulation and a clean offline characterization, but Theorem 1's proof has a 256x constant error in N0 and the imported [28] guarantees are used under resets without proof—both need fixing before acceptance.","tokens_in":21930,"tokens_out":3847,"would_cite":true,"duration_ms":38260,"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":"When crowd workers improve with experience, a cost-aware bandit algorithm can keep total regret logarithmic in the budget.","keywords":["crowdsensing","worker recruitment","multi-armed bandits","budget constraint","non-stationary rewards","learning curves","change-point detection","cost-aware UCB"],"falsifier":"The most direct check is to take the two-worker instance used in the experiments, with one fast-learner and one slow-learner, and compute the regret of CATI-UCB for budgets up to 10^5. If the regret, after subtracting constant terms, does not stay within a slowly growing O(log B) envelope — or if it matches a power law — the central claim is refuted. A sharper check is to examine the proof of the imported concentration inequality and verify that it still holds when N_{i,t} is reset to 1 at saturation; if it needs N_{i,t} to be monotonically increasing, the theorem is invalid.","tokens_in":20951,"feed_emoji":"🎯","tokens_out":5737,"duration_ms":57141,"temperature":0.7,"pith_summary":"This paper studies budget-constrained mobile crowdsensing recruitment when a worker's sensing quality improves with each task and then plateaus, and when each worker's cost is unknown. The authors claim that the offline optimum is essentially to spend the whole budget on the worker with the highest converged reward-per-cost ratio, up to a constant loss. They design CATI-UCB, which learns each worker's early learning curve, detects when performance saturates, and ranks workers by an upper-confidence estimate of reward divided by a lower-confidence cost estimate. They prove a regret bound for CATI-UCB of O(log B) relative to an oracle that knows all trajectories and costs, and they show empirically that it beats baselines that ignore learning or assume known costs. The practical significance is that a platform can recruit novice workers who later become top performers without paying much more than if it knew their future in advance.","feed_headline":"When workers improve with practice, regret stays O(log B)","feed_subtitle":"A cost-aware bandit learns each worker's learning curve and focuses spending on the best reward-per-cost worker.","key_machinery":"The central object is the converged reward-to-cost ratio ρ_i = μ_i*/c_i. The algorithm maintains for each worker a piecewise linear model of the early reward trend, a running average cost, and a two-window comparison that fires a reset when the sliding-window means diverge. Selection uses the ratio of an optimistic reward estimate to a pessimistic cost estimate, with confidence terms of order sqrt(log(1/δ)/N_{i,t}). This ratio-symmetric optimism is what lets the algorithm concentrate budget on the worker with the best long-term efficiency.","core_discovery":"On the paper's own terms, the central discovery is that an increasing-then-converging reward trajectory, combined with unknown worker-specific costs, does not destroy the tractability of budgeted online recruitment. Lemma 1 shows that the optimal offline expected reward R*(B) satisfies ρ*B − C0 ≤ R*(B) ≤ ρ*B, where ρ* is the largest converged reward-per-cost ratio, so the single-worker policy that spends the whole budget on the worker achieving ρ* is optimal up to an additive constant. Theorem 1 states that the CATI-UCB policy — online least-squares fitting of the early linear trend, two-window change-point detection to reset after saturation, and selection by the ratio of reward UCB to cost","pith_inferences":["Implicitly, the analysis suggests that once worker costs are known, the learning-then-plateau structure reduces recruitment to estimating one scalar per worker — the converged ratio — so a simpler successive-elimination scheme might achieve similar regret without change-point detection; this is a testable conjecture the paper does not pursue.","The paper's sensitivity experiments show regret is non-monotonic in the detection window, so the constant C0 and the pre-plateau budget waste depend on how well the detector is tuned; one could derive a lower bound linking regret to the learning rate and noise variance, which the paper leaves open.","Because the denominator of the ratio uses a lower confidence bound of cost, the algorithm is sensitive to very cheap workers; a robust extension would be to treat costs as log-normal or to use a regularized ratio, though such extensions lie outside the paper's analysis."],"forward_implications":["If the logarithmic regret bound holds, a crowdsensing platform can run online recruitment with learning workers and unknown costs and lose only O(log B) in cumulative quality compared with an oracle that knows every worker's future trajectory.","The offline optimum result means that, asymptotically, only one worker matters: the one with the highest converged reward-per-cost ratio; all other workers contribute only a constant to the best possible utility.","The same machinery carries over to multiple task types, at the cost of slower estimation per (worker, task type) pair, and to combinatorial selection of up to m workers per round, because suboptimal subsets must contain at least one suboptimal worker.","Empirically, the algorithm outperforms baselines that ignore experience-driven dynamics or assume known costs on piecewise linear, negative exponential, and trace-driven data derived from a real crowdsourcing platform."],"fun_headline_variants":["Crowdsensing with learning workers: optimal under budget","Budgeted recruitment meets worker learning curves","Cost-aware bandits for workers who improve over time","Optimal crowdsensing when skills grow and costs vary"],"cache_read_input_tokens":2304,"weakest_assumption_plain":"The logarithmic regret proof relies on confidence-interval and change-detection bounds taken from an earlier paper, and the algorithm resets a worker's sample count to 1 whenever it thinks the worker has plateaued. If those earlier bounds require a continuously growing sample count without such resets, the proof collapses. Separately, the threshold N0 used in the theorem is about 256 times too small to make the proof's inequalities hold, so the proof as written would need a l","fun_headline_variants_meta":{"raw":{"variants":["Crowdsensing with learning workers: optimal under budget","Budgeted recruitment meets worker learning curves","Cost-aware bandits for workers who improve over time","Optimal crowdsensing when skills grow and costs vary"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000153,"raw_usage":{"total_tokens":1072,"prompt_tokens":797,"completion_tokens":275,"prompt_tokens_details":{"cached_tokens":256},"prompt_cache_hit_tokens":256,"prompt_cache_miss_tokens":541,"completion_tokens_details":{"reasoning_tokens":214}},"tokens_in":541,"tokens_out":275,"duration_ms":4170,"temperature":1.0,"reasoning_tokens":214,"cache_read_input_tokens":256,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-02T04:51:58.828314+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"The most direct check is to take the two-worker instance used in the experiments, with one fast-learner and one slow-learner, and compute the regret of CATI-UCB for budgets up to 10^5. If the regret, after subtracting constant terms, does not stay within a slowly growing O(log B) envelope — or if it matches a power law — the central claim is refuted. A sharper check is to examine the proof of the imported concentration inequality and verify that it still holds when N_{i,t} is reset to 1 at saturation; if it needs N_{i,t} to be monotonically increasing, the theorem is invalid.","supporting_citations":[],"review_version":1}