{"id":"f0142a20-8302-47c0-80b4-867e78eaf08b","arxiv_id":"2509.04296","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":5.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":3,"one_line_summary":"AT-UCB uses a cheap abstracted causal model to filter out suboptimal actions before running UCB on the expensive base model, with a regret bound that improves when the abstraction is accurate.","lead":"This paper introduces AT-UCB, an algorithm that first tries cheap coarse-grained versions of a decision problem to rule out bad choices, then runs a standard bandit algorithm on the remaining choices in the expensive detailed model. It provides a regret bound and a small epidemic-simulation test showing lower regret than plain UCB when the coarse model is accurate enough.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Proposition 1 and the AT-UCB regret guarantee silently assume the abstract optimal arm has a base preimage; without an explicit surjectivity/attainability condition, the filter can delete the true optimal base arm and the regret bound fails.","rationale":"The reader's weakest assumption is exactly the load-bearing point. The paper's main theoretical claim, Proposition 2, relies on Proposition 1 to ensure that the optimal base action survives the abstract-level filtering. Without a surjectivity/attainability condition on ω, the abstract optimal arm may have no base preimage, forcing D^c to exclude the image of the true optimal arm and breaking the regret bound in the worst case. The counterexample shows the issue is not merely a proof gap but a genuine failure of the stated theorem under the paper's own Definition 4. I agree with the reader's assessment: the core idea is sound once the missing condition is added, and the paper's experiments use a surjective ω, so the empirical illustration is unaffected. Other limitations (need to know ε(α), Assumption 1 requiring gap knowledge) are openly acknowledged in Appendix D and are practical rather than correctness threats. Therefore the verdict should remain CONDITIONAL, i.e. no change from the reader's verdict.","tokens_in":12272,"tokens_out":14125,"duration_ms":124403,"concrete_test":"Analytically test Proposition 1 on the explicit counterexample: A={a1,a2}, A'={a1',a2'}, base rewards both 0, abstract rewards µ_{a1'}=100, µ_{a2'}=0, ω(a1)=ω(a2)=a2'. With s=e=0, Eq. (3) asserts µ_{a2'} ≥ µ_{a1'}, i.e. 0 ≥ 100, so the proposition fails because a1' has no preimage. If the authors intended the cited τ-ω definition to include surjectivity, they should amend Definition 4 accordingly and re-verify the proof under that assumption.","verdict_should_be":"UNCHANGED","load_bearing_attack":"Proposition 1 (Eq. 3) is the foundation for the action-restriction argument: it justifies defining D via Eq. (4) and guarantees that the optimal base arm a1 is not eliminated on the abstract level. The proof applies Lemma 2 to 'ak ∈ ω^{-1}(a'_1)', but Definition 4 only states ω : A → A′; it never asserts that a'_1 has a preimage or that ω is surjective. If a'_1 ∉ ω(A), no such ak exists and the derivation collapses. This is not a purely cosmetic gap: take an exact abstraction (s(α)=e(α)=0) with two base actions both having mean reward 0, abstract actions a'_1 (mean 100) and a'_2 (mean 0), and ω(a)=a'_2 for both base actions. Since consistency is only checked on ω(A), all abstraction-error definitions are satisfied, yet Eq. (3) would imply µ_{ω(a1)} ≥ µ_{a'_1}=100, which is false. With ε=ϵ(α)=0, D={a'_2}, D^c={a'_1}, and ω^{-1}(D^c)=∅: the UCB phase either has an empty action set or falls back to unspecified behavior, and the bound in Proposition 2 (Eq. 7) cannot hold. The minimal repair is to add the explicit assumption that ω is surjective, or at least that a'_1 ∈ ω(A), to the hypotheses of Proposition 1 and to Assumption 1/Algorithm 1. This is a real restriction when the abstract model contains behaviors or interventions not realizable in the base model.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper proposes AT-UCB, an algorithm for causally abstracted multi-armed bandits (CAMABs) that first uniformly explores a cheap, coarse-grained abstract bandit, uses the resulting reward estimates to discard abstract actions that appear suboptimal relative to the best observed mean minus a threshold ε, and then runs UCB on the base actions whose abstract image survives the filter. The main theoretical contribution is Proposition 2, an expected regret bound of the form n′C + 3Σ_{a∈ω^{-1}(D^c)} Δ_a + Σ_{a∈ω^{-1}(D^c), Δ_a>0} 16 log(n)/Δ_a + 2 max_a Δ_a, claimed to improve on standard UCB when the abstraction is accurate enough that |ω^{-1}(D^c)| ≪ k. The paper also reports a small experiment on SIR epidemic simulators with k=10 base regions and k′=4 abstract regions, showing lower empirical regret for small ε. The theoretical analysis is conditional on Proposition 1 and Assumption 1, which relate the abstraction errors to the abstract optimality gaps.","tokens_in":12695,"tokens_out":11892,"duration_ms":121259,"significance":"If the theory is repaired, this is a useful contribution to the CAMAB literature: it addresses the inverse direction (abstract-to-base transfer), which is less studied than the base-to-abstract direction in prior work by Zennaro et al., and it gives a clean conditional regret bound rather than only heuristics. The paper is transparent about several limitations, especially in Appendix D, and the proof strategy is largely standard. The central claim, however, currently rests on a missing attainability/surjectivity condition and on assumptions that are not well-defined in edge cases; these issues are load-bearing rather than cosmetic. With explicit separation and attainability conditions, and with a clearer statement about the oracle knowledge needed to set ε and n′, the result would be a solid, publishable contribution.","major_comments":[{"comment":"The proof of the left inequality applies Lemma 2 to 'a_k ∈ ω^{-1}(a'_1)', but Definition 4 only gives ω: A → A′ and never asserts that a′_1 is in the image of ω. If a′_1 has no base preimage, the proof is invalid and the statement can be false. For example, take an exact abstraction (s(α)=e(α)=0) with two base arms both of mean 0, abstract arms of means 100 and 0, and ω mapping both base arms to the abstract arm of mean 0. All abstraction-error definitions are satisfied, yet Eq. (3) would require 0 ≥ 100. This is not cosmetic: under Algorithm 1 with ε=ε(α), the set ω^{-1}(D^c) can be empty or can exclude the true optimal base arm, so the regret bound in Proposition 2 cannot hold. Please add an explicit attainability/surjectivity assumption (e.g., a′_1 ∈ ω(A), or ω surjective) to the hypotheses of Proposition 1 and consequently to Assumption 1/Algorithm 1.","section":"§3, Proposition 1 (Eq. 3) and Appendix B"},{"comment":"Assumption 1 is not well-defined when D = ∅, since min_{a′∈D} Δ′_{a′} is taken over an empty set; if interpreted as +∞, no finite n′ can satisfy the displayed lower bound. In addition, the right-hand side contains (ε(α)-Δ′_{ω(a1)})^{-2}; Proposition 1 only guarantees Δ′_{ω(a1)} ≤ ε(α). If equality holds, the denominator is zero and no finite n′ exists, so the phrase 'n′ sufficiently large' is not enough. The proof of Lemma 3 requires this quantity to be strictly positive. Please state the required separation conditions explicitly and handle the D=∅ case separately; in that degenerate case AT-UCB reduces to UCB on the full base action set and the second sum in Lemma 3 is empty.","section":"§3.1, Assumption 1 (Eq. 6) and Lemma 3"},{"comment":"The central regret guarantee is conditional on ε = ε(α) and on an n′ satisfying Assumption 1, both of which depend on quantities (ε(α), abstract optimality gaps) that the learner is assumed to know. The paper candidly acknowledges this in the Conclusion and Appendix D, but the limitation is load-bearing: the algorithm as stated takes a user-supplied ε, Figure 1 shows that performance degrades as ε increases, and no guidance is given for setting n′ without oracle knowledge. As written, the practical speed-up claim holds only under oracle tuning. Please state the result explicitly as a separation-type guarantee that includes the oracle requirement, and either discuss constructive choices for ε and n′ or clearly identify adaptive/parameter-free variants as open problems.","section":"§3, Proposition 2; §5 and Appendix D"}],"minor_comments":[{"comment":"In the restated Proposition 1 in Appendix B, the text says 'with IC error s(α) and RD error e(α)', which swaps the names from Definition 5 (where e is IC error and s is RD error). The definition of ε(α) is unaffected, but the naming should be consistent.","section":"Appendix B, Proposition 1 proof"},{"comment":"The comparison with the standard UCB bound is informal. Constants (16 vs. the usual 8) and the presence of surviving near-duplicate arms with very small gaps can affect the comparison. Please either make the comparison precise or label it as a heuristic motivating the algorithm.","section":"§3, text after Eq. (7)"},{"comment":"The experimental evaluation is limited to one configuration (k=10, k′=4, n=100, n′=20, 10 repeats) and a single plot. A sensitivity analysis over n′, over the abstraction errors, and across different reward distributions would substantially strengthen the empirical claim. The captions could also define the plotted quantities more explicitly.","section":"§4, Experiments"},{"comment":"The paper states that code will be released upon acceptance. Providing a public repository at submission time, or at least pseudocode with exact parameter choices, would improve reproducibility.","section":"§4, Code availability"}],"recommendation":"major_revision","confidential_remarks":"The paper is a competent contribution to the CAMAB line and the main proof gap (the missing preimage/surjectivity condition in Proposition 1) is repairable by adding an explicit assumption. I would not reject the paper; the revision should make the attainability and separation conditions precise, handle the D=∅ case, and be honest about the oracle knowledge needed to set ε and n′. The self-citation of Zennaro et al. is appropriate, and the inverse-direction result is not circular."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"The genuinely new thing here is the direction: instead of transferring information from base to abstract model, AT-UCB uses a cheap abstract bandit to filter actions before running UCB on the expensive base model. That inversion is not in the Zennaro et al. CAMAB paper, and the regret bound in Proposition 2 is a legitimate extension. The algorithm itself is simple—uniform exploration, thresholding, UCB on surviving preimages—but that simplicity is a virtue for a first result in this setting. The writing is clear, and the authors are candid about the practical limitations in Appendix D: they know that n' requires unknown gaps, that epsilon(alpha) is usually unknown, and that they don't use the causal graph for exploration. That honesty counts for something.\n\nThe soft spots are real but mostly proportionate to the paper's scope. First, the stress-test note is correct and matters: the proof of Proposition 1 applies Lemma 2 to an arm a_k in omega^{-1}(a'_1) without ever stating that this set is nonempty. If the abstract optimal arm has no base preimage, the bound can fail badly, and the filter can delete the true optimal base arm. The counterexample with both base arms mapping to the suboptimal abstract action is a valid illustration. This is load-bearing in the sense that the regret guarantee rests on it, but it's a one-line repair: add surjectivity of omega, or at minimum a'_1 in omega(A), to the hypotheses. The authors should flag it as a modeling assumption.\n\nSecond, the empirical work is thin. One SIRS model, 10 repeats, no released code. For a theory-first paper that's acceptable, but it limits what we can conclude about how often the speedup actually materializes. The authors don't overclaim—they say the advantage depends on the abstraction being accurate and epsilon being known.\n\nThird, the self-citation is fine. Lemma 1 comes from their prior work, but the inverse-direction algorithm and its regret bound are not a dressed-up restatement.\n\nWho is this for? People working on causal abstraction, multi-fidelity optimization with simulators, or warm-started bandits. It's a reasonable, honest contribution that deserves referee time. I'd like to see the surjectivity assumption added, code released, and ideally a second experiment that varies epsilon to show sensitivity. As is, a conditional accept is fair.","headline":"A clear, honest paper extending CAMABs to the inverse abstraction direction; the regret bound is a real contribution, but the proof of Proposition 1 quietly assumes the abstract optimal arm has a base preimage—an easy fix that nevertheless needs to be stated.","tokens_in":13119,"tokens_out":1469,"would_cite":true,"duration_ms":16370,"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":"The paper proposes AT-UCB, which uses cheap abstract causal models to filter arms before UCB, and proves a regret bound that beats standard UCB when the surviving action set is small.","keywords":["causal multi-armed bandits","causal abstraction","regret bound","arm filtering","UCB algorithm","abstraction error","epidemic simulation","thresholding bandits"],"falsifier":"Construct a two-level bandit with abstract arms a'_1 and a'_2 whose means differ by more than epsilon, where a'_1 has no base preimage and every base arm maps to a'_2. Let AT-UCB explore the abstract model long enough to satisfy its sample-size assumption; if it then classifies a'_2 as sub-threshold and never selects the true base optimal arm, the Proposition 1 bound is violated and the predicted regret reduction does not occur.","tokens_in":12213,"feed_emoji":"🎰","tokens_out":5961,"duration_ms":58199,"temperature":0.7,"pith_summary":"The paper tries to show that when a decision problem has both a cheap, coarse causal model and an expensive, fine-grained one, the cheap model can be used before learning to eliminate bad actions, so that an upper-confidence-bound learner only pays regret over a small surviving set. It proposes AT-UCB and gives a regret bound stating that total expected regret is roughly the abstract exploration cost plus UCB regret over the surviving base actions, which beats classic UCB when the surviving set is much smaller than the full action set. The practical upshot for simulators in epidemiology and similar fields is that a small budget spent on a fast approximate model can shrink the search space before spending expensive simulation budget on plausible interventions.","feed_headline":"Cheap abstract models can pre-filter arms and cut bandit regret","feed_subtitle":"AT-UCB explores a coarse causal model first, then runs UCB only on surviving actions, lowering cumulative regret.","key_machinery":"The threshold epsilon(alpha) = 2(s(alpha)+e(alpha)), built from the abstraction's interventional consistency error and reward discrepancy error, is the central object. It converts two distribution-level measures of how faithful the coarse model is to the fine model into a single action-filtering threshold: abstract actions whose estimated means fall more than epsilon below the abstract best are discarded, and only base actions mapping to the remaining abstract actions enter the UCB phase.","core_discovery":"The central claim is that causal abstraction gives a principled, quantitative way to transfer knowledge from a cheap approximate model to an expensive base model, with guarantees. For an abstraction with interventional consistency error e(alpha) and reward discrepancy error s(alpha), Proposition 1 bounds the abstract mean of the image of the true base optimal arm: it lies within epsilon(alpha) = 2(s(alpha)+e(alpha)) of the abstract optimal mean. This justifies defining a candidate set of abstract actions whose means are within epsilon of the abstract best, then restricting the base search to base actions mapping into that set. AT-UCB estimates abstract means by uniform exploration, removes a","pith_inferences":["Because the paper never states that the intervention map omega is surjective, a natural strengthening is to define the candidate set over abstract actions that have at least one base preimage; this would preserve the regret bound even when the abstract optimum has no fine-grained counterpart.","The regret guarantee depends on knowing epsilon exactly; a testable extension is to estimate epsilon online during the abstract exploration phase, since in practice the abstraction errors are often unavailable in advance.","AT-UCB ignores the causal graph structure inside the base and abstract models; combining its arm-filtering step with causal-bandit algorithms that exploit d-separators could reduce the abstract exploration cost further.","The thresholding mechanism is generic: any bandit setting with a relative threshold derived from an error bound could reuse AT-UCB's structure, so the result may extend beyond causally abstracted multi-armed bandits."],"forward_implications":["Decision-makers with multi-fidelity simulators can allocate a small exploration budget to the cheap model and then restrict expensive simulation to a small candidate action set, reducing cumulative regret when the abstraction is accurate.","The regret bound scales with the number of surviving base actions rather than the total number of base actions, so the gain grows as the abstraction becomes more faithful and the surviving set shrinks.","Even approximate abstractions with nonzero consistency and reward-distortion errors yield a working algorithm, provided the errors are known well enough to set epsilon.","The bound reduces to the standard UCB bound as a special case when the surviving set is the full action set, so AT-UCB is never worse in the bound when abstraction quality is poor.","The same filter-then-UCB pattern applies to any problem with a coarse simulator related to a fine simulator by an approximate causal abstraction, such as agent-based epidemic models paired with differential-equation models."],"supporting_citations":[{"why":"Introduces the CAMAB framework and supplies Lemma 1 (their Proposition 4.1), the bound |mu_a - mu_{omega(a)}| <= s(alpha)+e(alpha) that all subsequent propositions build on.","marker":"[Zennaro et al., 2024]"},{"why":"Provides the (tau, omega)-abstraction formalism and consistency notion that define the interventional consistency error used in the threshold.","marker":"[Rubenstein et al., 2017, Beckers and Halpern, 2019]"},{"why":"Supplies the standard UCB algorithm and its regret bound that AT-UCB inherits when run on the restricted surviving action set.","marker":"[Lattimore and Szepesvári, 2020]"},{"why":"Defines causal multi-armed bandits as decision problems over interventions in structural causal models, giving the base problem formulation.","marker":"[Bareinboim et al., 2015]"},{"why":"Establishes the causal bandit setting and the notion of learning good interventions via causal inference, which AT-UCB extends with abstraction-based filtering.","marker":"[Lattimore et al., 2016]"}],"fun_headline_variants":["Cheap abstract models pre-filter actions to cut bandit regret","Pre-filter bandit arms with abstract models, cut regret","Accelerate bandit decisions via causal abstraction shortcut","Abstract models guide UCB to lower regret in bandits","Causal abstraction prunes bandit arms, speeds decisions"],"cache_read_input_tokens":2688,"weakest_assumption_plain":"The proof depends on the best simplified action being the image of at least one fine-grained action; if the best simplified action has no fine-grained counterpart, the algorithm can eliminate the true best fine-grained action and the regret guarantee no longer holds.","fun_headline_variants_meta":{"raw":{"variants":["Cheap abstract models pre-filter actions to cut bandit regret","Pre-filter bandit arms with abstract models, cut regret","Accelerate bandit decisions via causal abstraction shortcut","Abstract models guide UCB to lower regret in bandits","Causal abstraction prunes bandit arms, speeds decisions"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000328,"raw_usage":{"total_tokens":1640,"prompt_tokens":686,"completion_tokens":954,"prompt_tokens_details":{"cached_tokens":256},"prompt_cache_hit_tokens":256,"prompt_cache_miss_tokens":430,"completion_tokens_details":{"reasoning_tokens":873}},"tokens_in":430,"tokens_out":954,"duration_ms":6567,"temperature":1.0,"reasoning_tokens":873,"cache_read_input_tokens":256,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-05T10:13:16.889142+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Construct a two-level bandit with abstract arms a'_1 and a'_2 whose means differ by more than epsilon, where a'_1 has no base preimage and every base arm maps to a'_2. Let AT-UCB explore the abstract model long enough to satisfy its sample-size assumption; if it then classifies a'_2 as sub-threshold and never selects the true base optimal arm, the Proposition 1 bound is violated and the predicted regret reduction does not occur.","supporting_citations":[{"cited_title":"Causal consistency of structural equation models","cited_arxiv_id":null,"evidence_quote":"Provides the (tau, omega)-abstraction formalism and consistency notion that define the interventional consistency error used in the threshold."},{"cited_title":"Bandits with unobserved confounders: A causal approach","cited_arxiv_id":null,"evidence_quote":"Defines causal multi-armed bandits as decision problems over interventions in structural causal models, giving the base problem formulation."},{"cited_title":"Causal bandits: Learning good interventions via causal inference","cited_arxiv_id":null,"evidence_quote":"Establishes the causal bandit setting and the notion of learning good interventions via causal inference, which AT-UCB extends with abstraction-based filtering."}],"review_version":1}