△ Mechanism confirmed, baseline not beaten 2026

Median-of-Means Bellman Targets

Implementation & benchmark of arXiv:2607.20822 — Robust Asynchronous Q-Learning under Reward and State Corruption via Batching

Usefulness8/10

Difficulty4/10

Novelty6/10

Training Stability Accuracy Sample efficiency Rl Loss Training Probability Statistics Optimization Stochastic processes

Source paper: Robust Asynchronous Q-Learning under Reward and State Corruption via Batching arXiv:2607.20822 ⓘ · analyzed Aug 30, 2026

AI-generated research hypothesis, automatically tested. Not peer-reviewed.

Idea description

Replace the ordinary average of bootstrapped Q-learning targets by a median-of-means estimator. For each current state-action anchor, divide repeated transition samples into blocks, average the target within each block, and take the median of the block averages; a minority of arbitrarily corrupted reward or next-state observations then affects fewer than half of the block estimates. For neural Q-learning, the same construction can be applied either to repeated samples for identical or nearby state-action anchors, or to minibatch gradients when exact repeated anchors are unavailable.

Formulas

$$\mathbb{P}(|T_2|\ge t\mid |\mathcal{S}|=j)\le 2\exp\left(-\frac{2t^2}{j(\overline{\Gamma}-\underline{\Gamma})^2}\right),$$

$$q\le 2\exp\left(-\frac{2t^2}{M(\overline{\Gamma}-\underline{\Gamma})^2}\right)\le \delta/4,$$

$$\bar y_b=\frac{1}{m}\sum_{i\in b}y_i,\qquad \widehat{T}_{\mathrm{rob}}=\operatorname{median}_{b=1}^{B}\bar y_b,\qquad y_i=\operatorname{clip}\left(r_i+\gamma\max_{a'}Q_{\theta^-}(s'_i,a'),\underline{\Gamma},\overline{\Gamma}\right),$$

$$L_{\mathrm{rob}}(\theta)=\frac{1}{K}\sum_{k=1}^{K}\left(Q_\theta(s_k,a_k)-\widehat{T}_{\mathrm{rob}}(s_k,a_k)\right)^2.$$

Mathematical statement

The paper's concentration argument conditions on the number of samples and applies Hoeffding's inequality to bounded observations. In the extracted proof, for a random subset $\mathcal{S}$ of size $|\mathcal{S}|=j$, a bounded sum $T_2$, and target range $[\underline{\Gamma},\overline{\Gamma}]$, it uses $\mathbb{P}(|T_2|\ge t\mid |\mathcal{S}|=j)\le 2\exp(-2t^2/[j(\overline{\Gamma}-\underline{\Gamma})^2])$, followed by the worst-case bound at $j=M$. Here $M$ is the maximum number of observations, $t$ is a deviation threshold, and $\underline{\Gamma},\overline{\Gamma}$ bound each clean contribution. The robust estimator used below is the median-of-means: with $B$ blocks of size $m$, block means $\bar y_b=m^{-1}\sum_{i\in b}y_i$, and $n=Bm$, output $\operatorname{median}_{b\le B}\bar y_b$. If fewer than $B/2$ blocks contain corrupted samples and clean targets have range width $\Gamma=\overline{\Gamma}-\underline{\Gamma}$, the median remains controlled by the clean-block deviation, while ordinary averaging can have unbounded adversarial influence. For a discounted bounded-reward MDP, use $\underline{\Gamma}=-R_{\max}/(1-\gamma)$ and $\overline{\Gamma}=R_{\max}/(1-\gamma)$ after clipping targets.

Implementation notes

(1) Integration point: modify the target-construction line in DQN, Double-DQN, or an offline Q learner. Do not average one target per transition directly. Construct groups of $n=Bm$ transitions sharing the same current state-action anchor; in continuous environments, create anchors by discretized state hashes, replay-buffer nearest-neighbor clusters, or multiple rollouts from the same simulator state. Compute target-network values with the usual Double-DQN action selection, clip every target to $[\underline{\Gamma},\overline{\Gamma}]=[-R_{\max}/(1-\gamma),R_{\max}/(1-\gamma)]$, and robustly aggregate them. (2) Pseudocode: inputs are grouped transitions $G_k=\{(s_k,a_k,r_i,s'_i)\}_{i=1}^{Bm}$. For each group, set $y_i=\operatorname{clip}(r_i+\gamma Q_{\theta^-}(s'_i,\arg\max_aQ_\theta(s'_i,a)),\underline{\Gamma},\overline{\Gamma})$; randomly partition the targets into $B$ blocks of size $m$; calculate $u_b=m^{-1}\sum_{i\in b}y_i$; set $\widehat T_k=\operatorname{median}(u_1,\ldots,u_B)$; minimize $K^{-1}\sum_k(Q_\theta(s_k,a_k)-\widehat T_k)^2$. Use stop-gradient through $\widehat T_k$. (3) Mathematical versus empirical quantities: $\gamma$, $R_{\max}$, $B$, and $m$ are chosen hyperparameters; the Hoeffding deviation threshold can be set as $t=\Gamma\sqrt{M\log(8/\delta)/2}$ for a desired confidence level, but the actual corruption fraction and clean variance should be measured empirically. If exact anchor groups are unavailable, use coordinate-wise median aggregation of per-block gradients as a fallback and compare it separately. (4) First experiment: train a small CartPole or MiniGrid DQN and an offline Atari-style toy dataset with injected reward outliers and random next-state replacements at corruption rates $0,0.05,0.10,0.20$. Compare ordinary mean targets, clipped mean targets, and median-of-means with $B\in\{5,9\}$, $m\in\{4,8,16\}$, using identical replay and optimizer settings. Measure return, clean-test Bellman error, Q-value divergence, and loss variance. Success is lower degradation and fewer catastrophic Q spikes under corruption, while matching the baseline return and wall-clock cost in the clean setting.

Verification

Mechanism confirmed, baseline not beaten

Stage 1 · Toy mechanism gate: Passed ✓

Stage 2 · Mechanism transferred to benchmark: Confirmed ✓

Stage 2 · Practical benchmark result: Inconclusive

Methodology: 8 paired seeds, permutation test (p<0.05) against a learning-rate-tuned baseline. How verification works

Stage 1 — Mechanism check agent confidence 8/10

Built a readable median-of-means Bellman-target prototype with clipping, a Hoeffding sanity check, corruption-boundary sweeps, clean-sample scaling, and a small fitted-target comparison. The mechanism manifested: with B=9, MoM remained substantially more robust through 4 corrupted blocks and failed at the predicted majority boundary of 5 blocks. Clean MoM RMSE had log-log slope -0.516 versus the predicted -0.5, and corrupted regression target MSE was lower than the ordinary mean.

Agent confidence: 8/10

Baseline: Ordinary mean: absolute error 0.445 at 4/9 corrupted blocks; corrupted regression target MSE 3.53e-04; clean fitted-function MSE 2.05e-05.
Idea: Median-of-means: absolute error 0.171 at 4/9 corrupted blocks and bias 1.0 at 5/9; corrupted regression target MSE 3.95e-05; clean fitted-function MSE 3.20e-05; clean RMSE scaling slope -0.516.

Limitations: This is a synthetic repeated-anchor Bellman-target analogue, not a full CartPole or DQN training run. Corruptions were blockwise and targets were clipped to [-1,1]; continuous-state grouping, randomly scattered corruption, wall-clock overhead, and end-to-end RL returns were not tested.

How to run: python3 mom_experiment.py

Stage 2 — Benchmark vs. tuned baseline (arXiv:2607.20822) Sep 2, 2026

No significant difference vs. the tuned baseline (+5.7%, p=0.5372, wins 2 / 8 paired seeds).

Benchmark: Dynamics forecasting
Model: rnn_small
Paired seeds: 8
Baseline mean: 0.0011
Idea mean: 0.0011
Effect (Δ): 0.0001 (+5.7%; negative = idea better)
Wins: 2 / 8 paired seeds
p-value: 0.5372 (permutation test, 20 000 shuffles)
Smallest detectable effect: n/a
Mechanism: Confirmed ✓
Practical effect: Inconclusive
Baseline tuning: swept over 3 configs

Limitations:

The built-in dynamics track is supervised rollout regression, not an end-to-end DQN with repeated Bellman transition anchors; therefore the permitted coordinate-wise median-gradient fallback was tested. Reward corruption, replay grouping, wall-clock overhead, and literal Bellman-target aggregation were not tested.

How to run: python3 stage2_bench.py

Verdict computed by deterministic test code from paired-seed statistics — not by the language model.

Stage 2 — Benchmark Aug 30, 2026 latest Failed ✗

Agent confidence: 9/10

Implemented coordinate-wise median aggregation of per-block gradients as the permitted fallback for Median-of-Means Bellman Targets on the structurally matched dynamics track. The mechanism held at neural-network scale, but the idea was slightly worse on clean test MSE and not statistically significant.

Baseline: rnn_small dynamics, best lr=0.006: mean test MSE 0.0010542348 over 8 paired seeds.
Idea: median-gradient rnn_small, best lr=0.006 and B=9: mean test MSE 0.0011142973; paired delta +0.0000600626, p=0.5372, 2/8 wins. Corrupted-gradient shift was 8.2032 for the ordinary mean versus 0.0180333 for the median, confirmed=true.

Benchmark result