{"id":"a7b9e4c5-a81f-45cc-9c78-196245da56c6","arxiv_id":"2411.13116","paper_version":1,"verdict":"REJECT","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"high","formal_verification":"none","parameter_count":4,"one_line_summary":"LCBT is a trajectory-only tree-search attack that claims to steer continuous-action RL agents to target policies with sublinear attack cost, but the proof of the claim has a serious importance-sampling flaw.","lead":"This paper introduces attacks that tamper with a reinforcement learning agent's actions during training, with both a white-box oracle method and a black-box tree-search method called LCBT. The authors give attack-cost bounds and experiments on DDPG, PPO, and TD3 in continuous control tasks. The black-box theoretical bound, however, rests on an invalid importance-sampling argument.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Theorem 2's proof relies on an invalid importance-sampling identity: P(ea|pi_o)=I{ea in A†} is not a probability distribution, so the LCB estimator in Eq. (3) is biased and the claimed sublinear attack cost does not follow.","rationale":"The reader's weakest_assumption identifies the same load-bearing concern: the lower-confidence-bound estimates are claimed to be valid lower bounds on Q_o for out-of-target actions, but the proof of Lemma 2 uses an importance-sampling identity that fails because P(ea|pi_o) is an indicator, not a probability distribution. I agree with this assessment. The paper's entire black-box attack guarantee rests on the LCB being a high-probability lower bound on Q_o; if the estimator is biased, the Hoeffding-based confidence interval is invalid, and the subsequent algebra in Lemma 3 and Theorem 2 cannot recover the sublinear cost bound. The empirical sections do not remedy this, as they demonstrate behavior of the algorithm without validating the theoretical estimator's unbiasedness. No other concern is as fundamental: the tree-expansion and complexity arguments, while possibly loose, are secondary to the correctness of the Q-estimator. With the central theorem unsupported, the reader's REJECT verdict is appropriate, and no verdict change is needed.","tokens_in":34397,"tokens_out":2953,"duration_ms":30742,"concrete_test":"Construct a deterministic finite-horizon MDP with two actions, a1 in A† and a2 not in A†, where pi_o always selects a1, rewards are positive for both actions, and the behavior policy b selects a2 whenever the agent proposes a2 (i.e., the attacker replaces a2 with a2). Then for every episode used to update the node representing a2, rho = I{a2 in A†} = 0, so Eq. (3) yields hatQ = 0. Compute E[hatQ] from the recursion in Appendix J and compare with Q_o(s,a2); they differ whenever rewards are nonzero, contradicting Eq. (15). This single calculation settles whether the importance-sampling identity holds.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central black-box guarantee (Theorem 2) depends on Lemma 2, which bounds the error of the Q-value estimator hatQ in Eq. (3). That estimator uses the importance ratio rho = prod_h P(ea_h|pi_o) / P(ea_h|b_h), and the paper sets P(ea_h|pi_o) = I{ea_h in A†_h(s)}. This is not a probability distribution: its values are 0 or 1 and do not sum to 1. More importantly, for any attacked step where the replacement action lies outside A† (the very regime the attack exploits), P(ea|pi_o)=0, so rho=0 for the entire episode. The paper asserts V_o_h(s) = E[rho G | s_h=s] and uses this to claim E[hatQ] = Q_o(s,a) in Eq. (15) of Appendix J. But if the behavior policy b_h assigns positive probability to out-of-target actions, the conditional expectation E[rho G | s_h=s, a_h=a] must be computed under a distribution that gives zero weight to those trajectories; it does not equal Q_o(s,a) for out-of-target actions. In fact, if the attacker always replaces an out-of-target action with another out-of-target action, rho is identically zero on the relevant trajectories, making E[hatQ]=0 rather than Q_o(s,a). Consequently, the Hoeffding bound in Lemma 2 does not apply to a biased estimator, Lemma 3 collapses, and the derivation of Eq. (7) in Theorem 2 is unsupported. This is a load-bearing flaw in the proof of the paper's headline result.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies training-time action-manipulation attacks against reinforcement learning in continuous state and action spaces. It defines a threat model in which the attacker replaces the agent's actions to steer the agent toward a target policy set, and it proposes two attacks: a white-box \"oracle\" attack that replaces out-of-target actions with the worst action under the best policy in the target set, and a black-box algorithm called LCBT that uses a binary cover tree of the action space, lower-confidence-bound estimates of Q-values, and importance sampling. The main theoretical claim is that LCBT forces an agent with sublinear dynamic regret to mostly act according to the target policy set with sublinear attack cost, O(R(T) + M H^3 K^E log(MT)) with E<1. Experiments on DDPG, PPO, and TD3 in three continuous-control environments show convergence of rewards to the target-policy level and high action-similarity percentages.","tokens_in":34800,"tokens_out":10346,"duration_ms":113514,"significance":"If the black-box bound were correct, it would be a substantial advance: prior action-manipulation results were mostly restricted to tabular settings or required model/algorithm knowledge, whereas Theorem 2 promises sublinear attack cost in continuous spaces from trajectory information alone. The threat model is clearly stated, the target-action-space formalism is reasonable, and the white-box oracle analysis appears internally coherent. The paper also makes a genuine attempt to define a sample-complexity notion of attack cost. However, the central black-box guarantee rests on an importance-sampling identity that is not valid as written, so the headline sublinear-cost theorem is not established. The experiments are suggestive but do not compensate for the proof gap, and no code or baselines are provided.","major_comments":[{"comment":"The proof of Lemma 2 asserts E[r_i + G^i rho^i | s_i, a_i] = Q_o(s_i, a_i), using the importance ratio rho defined from P(ea|pi_o) = I{ea in A-dagger}. This is not a probability distribution (or density) over the continuous action space, and it cannot serve as the Radon-Nikodym derivative for importance sampling. In particular, for any trajectory containing an attacked step whose replacement action lies outside A-dagger---the very situation the LCBT algorithm is designed to explore---the factor I{ea in A-dagger} is zero, so rho is identically zero for that episode. The conditional expectation in Eq. (15) is then taken under a measure that assigns zero weight to exactly the out-of-target actions the attack must evaluate; it does not equal Q_o(s,a_D,I). If the attacker replaces one out-of-target action by another (a common event during exploration), rho is zero on all relevant trajectories and the estimator receives no signal from those episodes. Consequently Lemma 2 bounds a biased estimator, Lemma 3 does not follow, and the derivation of Eq. (7) in Theorem 2 collapses. This is the load-bearing step for the black-box guarantee.","section":"Section 4.2, Eq. (3)-(4), Appendix J, Eq. (15)"},{"comment":"The definition of the behavior policy P(ea_h|s_h, b_h) is also not a well-defined conditional distribution. Eq. (4) assigns probability 1 to ea=a_k when a_k is in A-dagger and probability 1 to ea=a_{D,I} when a_k is not in A-dagger; these are events that depend on the agent's realized action a_k, not on the conditioning state s_h. For a stochastic agent policy, the actual data-generating distribution for ea_h is a mixture (with probability mass on a_k for target actions and on a_{D,I} for out-of-target actions), and the mixture weight---the agent's action probability---is missing from the denominator. The proof never specifies the filtration or the probability space with respect to which the expectation in Eq. (15) is taken, so the claimed unbiasedness of the estimator is not mathematically well-defined even apart from the normalization problem with I{ea in A-dagger}.","section":"Section 4.2, Eq. (4)"}],"minor_comments":[{"comment":"The abstract advertises an attack cost of O(R(T) + M H^3 K^E log(MT)), but Theorem 2, Eq. (7), contains M H^2 log(2MHK^2/delta_1) * sum_h |T^h_K|, which with the Appendix M bound |T^h_K| <= O(K^E) gives a leading term M H^2 K^E log(K), not M H^3 K^E log(MT). The H discrepancy should be reconciled.","section":"Abstract and Theorem 2, Eq. (7)"},{"comment":"The symbol K is used both for the total number of episodes and for the number of initial no-attack episodes (e.g., Algorithm 1, line 6, versus the statement of Theorem 2). This double use makes the cost bounds difficult to parse; distinct symbols should be introduced.","section":"Throughout, especially Algorithm 1 and Theorem 2"},{"comment":"The figure legends in the submitted text contain unencoded font tokens (strings such as \"/uni00000013/...\") instead of readable labels, making the experimental figures effectively uninterpretable. The figures should be regenerated with standard text encoding.","section":"Section 5, Figures 2, 3, and 6"},{"comment":"The experiments compare only oracle and LCBT attacks against the attack-free curve; they do not compare with existing continuous-space action-manipulation baselines such as LAS or the query-based attack discussed in Section 2, so the empirical advantage over prior methods is not quantified.","section":"Section 5"},{"comment":"There is a typo, \"sunlinear\" for \"sublinear\", in the sentence describing the attack cost results.","section":"Section 5, paragraph 1"}],"recommendation":"reject","confidential_remarks":"The white-box oracle analysis (Theorem 1) and the threat-model formulation are reasonable and could be the basis of a separate contribution. The problem is specific and technical: the black-box theorem's importance-sampling argument is invalid, and the flaw concerns the core estimator rather than a missing lemma or a presentation detail. I would be open to a revised submission if the authors can provide a corrected unbiased estimator---for example, using a properly normalized stochastic target policy with a known density and a well-defined behavior model---or if they explicitly downgrade Theorem 2 to a conjecture supported only by experiments."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Short version: this paper fills a real gap and has a plausible algorithm, but the headline black-box theorem is not proved. The definition P(ẽ|π_o)=I{ẽ∈A†} in Section 4.2 is not a proper conditional distribution — it assigns 1 to every in-target action and 0 to everything else. That invalidates the importance ratio ρ in Eq. (3) and the identity E[ρ G]=V_o used in Lemma 2. For any attacked step where the replacement action falls outside A† (exactly the regime the attack targets), ρ is identically zero on the executed trajectory, so the estimator in Eq. (3) does not estimate Q_o(s,a) at all. Lemma 2's Hoeffding bound therefore cannot be applied to a biased estimator, Lemma 3 collapses with it, and the derivation of Eq. (7) in Theorem 2 is unsupported. This is not a minor gap; the sublinear black-box cost is the paper's claimed contribution.\n\nWhat is genuinely good: the continuous action-manipulation problem with trajectory-only knowledge is real and under-studied. The oracle attack (Theorem 1) looks sound: with full MDP knowledge, replacing out-of-target actions with the worst action under π_o does make π_o look optimal, and the regret-to-cost bound is a reasonable application of Freedman's inequality. The LCBT tree structure and the idea of using LCBs to search for the worst action is a sensible heuristic, and the experiments (DDPG, PPO, TD3) show that something like this can steer policy learning in practice. The related-work table is honest about what existing methods require.\n\nSoft spots beyond the proof: no code or error bars, and the authors themselves note performance drops in higher dimensions (Environment 3 similarity drops to 52–65% under LCBT for DDPG). The attack cost plots are consistent with sublinear growth, but that is not a substitute for the missing proof.\n\nBottom line: I would not cite the sublinear black-box claim as established. But I would send this to a serious referee. The problem is important, the algorithm is not a trivial variant of existing work, and the flaw, while load-bearing, looks fixable: replace the indicator with a proper target distribution (or restrict estimation to trajectories that are entirely in-target and prove the bias is controlled). The paper as submitted is not ready. It deserves a rigorous review rather than a desk reject.","headline":"The oracle-attack half is fine, but the black-box LCBT guarantee rests on an importance-sampling definition that is not a probability distribution, so Theorem 2 does not go through.","tokens_in":35286,"tokens_out":3307,"would_cite":false,"duration_ms":34125,"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":"This paper claims that an attacker who only observes trajectories can force a continuous-action reinforcement-learning agent to learn a target policy with sublinear attack cost, provided the agent's dynamic regret is sublinear.","keywords":["action-manipulation attack","continuous reinforcement learning","black-box attack","Monte Carlo tree search","lower confidence bound","policy poisoning","dynamic regret","cyber-physical systems"],"falsifier":"Run LCBT on a one-step MDP with a very small target action set, compute $\\mathbb{E}[\\rho G \\mid s]$ under the real attacking behavior policy and compare it with $V^o(s)$; any systematic gap larger than the claimed Hoeffding radius would indicate that the LCB is biased and would invalidate the sublinear bound in Theorem 2.","tokens_in":34201,"feed_emoji":"🎯","tokens_out":5830,"duration_ms":58648,"temperature":0.7,"pith_summary":"This paper tries to establish that action-manipulation attacks on reinforcement learning remain cheap and effective when both states and actions are continuous. It proposes a black-box attack, LCBT, which uses only observed states, actions, and rewards to search for replacement actions, and proves that for any agent whose dynamic regret grows sublinearly, the attack forces the learned policy into an attacker-chosen target policy set with sublinear attack cost. It also gives a white-box oracle attack whose cost is bounded essentially by the agent's own regret. If the results are correct, a model-free attacker could steer continuous-control RL systems, such as cyber-physical controllers, toward dangerous policies during training while intervening on only a sublinear number of steps. The paper demonstrates the attack on DDPG, PPO, and TD3 in continuous environments.","feed_headline":"Black-box attack steers continuous RL at sublinear cost","feed_subtitle":"Watching only states, actions, and rewards, the attack pushes sublinear-regret agents to attacker-chosen policies.","key_machinery":"The mechanism is the Lower Confidence Bound Tree (LCBT): a binary action cover tree that recursively partitions the continuous action space, where each node $(D,I)$ carries a representative action $a_{D,I}$, a lower confidence bound $L^h_{D,I}(k)$ on $Q^o_h(s,a_{D,I})$, and a tighter bound $B^h_{D,I}(k)$ built from the children. The bounds combine importance-sampled trajectory returns with Hoeffding-style confidence radii plus structural terms $L_s d_s$ and $\\nu_1\\rho^D$ for state and action discretization. A traversal starting at the root repeatedly descends to the child with the smaller $B$-value, producing the replacement action; nodes are expanded when the confidence radius shrinks below the node's diameter. This machinery locates the worst action $a^-_h(s)$ without any model or algorithm knowledge, and the sublinear growth of the tree ($|\\mathcal{T}^h_K| = O(K^E)$) is what keeps the total attack cost sublinear.","core_discovery":"The central claim is Theorem 2: with probability at least $1-\\delta_1-\\delta_2$, the black-box LCBT attack forces an agent with sublinear dynamic regret to learn policies in the target policy set $\\Pi^\\dagger$, with attack cost $|\\tau|$ bounded by $O(D\\text{-Regret}(K) + M H^3 K^E \\log(MT))$, where $E = \\log_{2\\rho^{-2}} 2 < 1$. The attack works because, under the condition $\\Delta_{\\min} > 0$, replacing out-of-target actions with the worst actions for the target policy makes the agent perceive $\\pi^o$, the best policy inside the target set, as the optimal policy. The white-box oracle attack achieves the stronger bound $O(\\mathcal{R}(T))$ with full model knowledge, while the black-box bound adds a sublinear exploration cost for locating the worst action without knowing the MDP.","pith_inferences":["Editorial inference: if Theorem 2 is correct, then better-performing victims are cheaper to attack, because a smaller $D\\text{-Regret}(K)$ makes the first term in the attack-cost bound smaller; strong RL learners would be more vulnerable, not less.","Editorial inference: the tree-LCB construction is effectively a continuous-action bandit over the value gap $V^o - Q^o$, so the same idea could be adapted to reward poisoning or observation poisoning in continuous spaces.","Editorial inference: the condition $L_s d_s < \\Delta_{\\min}/2$ ties attack feasibility to how well the attacker can approximate the target policy's value, which suggests that a defender who smooths the Q-function or enlarges the gap could raise the attack cost.","Editorial inference: the dependence on the state-partition count $M$ makes the bound degrade in high-dimensional state spaces, so the practical attack cost in very large continuous environments is likely to exceed the sublinear ideal shown in low-dimensional experiments."],"forward_implications":["A black-box attacker with only trajectory access can induce policy convergence to the target set for any continuous RL algorithm whose dynamic regret is sublinear (Theorem 2).","The attack cost is $O(D\\text{-Regret}(K) + M H^3 K^E \\log(MT))$ with $E<1$, so the manipulation overhead beyond the victim's own regret is sublinear in the number of episodes.","The white-box oracle attack achieves attack cost $O(\\mathcal{R}(T))$ up to a $\\Delta_{\\min}$ denominator and a logarithmic factor, showing that full model knowledge removes the exploration term.","The empirical results show that under LCBT or the oracle attack, DDPG, PPO, and TD3-trained policies act inside the target action space in most test steps, with measured attack cost growing sublinearly.","The cover-tree size stays $O(K^E)$, giving time complexity $O(HK^{1+E}+HK\\log_{\\rho^{-2}}K)$ and space complexity $O(MHK^E)$."],"supporting_citations":[{"why":"Supplies the dynamic-regret definition and the sublinear dynamic-regret premise that Theorem 2 relies on.","marker":"[4]"},{"why":"Establishes the tabular LCB-H black-box action-poisoning attack cost bound that LCBT extends to continuous action spaces.","marker":"[17]"},{"why":"Provides the tabular multi-agent action-manipulation attack cost bound that this paper compares with in Table 1.","marker":"[18]"},{"why":"Shows a continuous action-space attack that requires model or algorithm knowledge, motivating the black-box setting.","marker":"[14]"},{"why":"Supplies Freedman's inequality, which the proof uses to convert regret bounds into attack-cost bounds in Theorem 1 and Theorem 2.","marker":"[31]"}],"fun_headline_variants":["Sublinear-cost attack steers continuous RL agents to target policies","Black-box attack forces continuous RL to learn attacker-chosen policies","Provable sublinear cost to manipulate continuous RL training","LCBT: sublinear-cost attack on continuous RL"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The attack's lower-confidence-bound estimates must be genuine lower bounds on the target policy's Q-values, but the proof of that uses an importance-sampling identity that drops exactly the trajectories where the attacker substituted an out-of-target action.","fun_headline_variants_meta":{"raw":{"variants":["Sublinear-cost attack steers continuous RL agents to target policies","Black-box attack forces continuous RL to learn attacker-chosen policies","Provable sublinear cost to manipulate continuous RL training","LCBT: sublinear-cost attack on continuous RL"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.001106,"raw_usage":{"total_tokens":4671,"prompt_tokens":1066,"completion_tokens":3605,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":682,"completion_tokens_details":{"reasoning_tokens":3538}},"tokens_in":682,"tokens_out":3605,"duration_ms":21224,"temperature":1.0,"reasoning_tokens":3538,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-12T16:49:54.948993+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Run LCBT on a one-step MDP with a very small target action set, compute $\\mathbb{E}[\\rho G \\mid s]$ under the real attacking behavior policy and compare it with $V^o(s)$; any systematic gap larger than the claimed Hoeffding radius would indicate that the LCB is biased and would invalidate the sublinear bound in Theorem 2.","supporting_citations":[{"cited_title":"Dynamic regret of policy optimization in non-stationary environments","cited_arxiv_id":null,"evidence_quote":"Supplies the dynamic-regret definition and the sublinear dynamic-regret premise that Theorem 2 relies on."},{"cited_title":"Efficient adversarial attacks on online multi-agent reinforcement learning","cited_arxiv_id":null,"evidence_quote":"Provides the tabular multi-agent action-manipulation attack cost bound that this paper compares with in Table 1."},{"cited_title":"Spatiotemporally constrained action space attacks on deep reinforcement learning agents","cited_arxiv_id":null,"evidence_quote":"Shows a continuous action-space attack that requires model or algorithm knowledge, motivating the black-box setting."},{"cited_title":"Freedman’s inequality for matrix martingales","cited_arxiv_id":null,"evidence_quote":"Supplies Freedman's inequality, which the proof uses to convert regret bounds into attack-cost bounds in Theorem 1 and Theorem 2."}],"review_version":1}