# Median-of-Means Bellman Targets

- ID: 1199
- Canonical URL: https://synthcore.org/idea/1199/median-of-means-bellman-targets
- API JSON: https://synthcore.org/api/idea/1199.json
- API Markdown: https://synthcore.org/api/idea/1199.md
- Verification status: mech_ok_no_baseline
- Source: [arXiv:2607.20822](https://arxiv.org/abs/2607.20822)
- Category: training
- Solves: stability, accuracy, sample-efficiency
- ML areas: rl, loss, training
- Math tags: probability, statistics, optimization, stochastic-processes
- Ratings: usefulness 8/10; difficulty 4/10; novelty 6/10

## 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.

## 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.

## Key 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.$$

## 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

- Status: mech_ok_no_baseline
- Mechanism evidence: yes
- Mechanism confirmed: yes
- Practical verdict: inconclusive
- Verdict: 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.

### Mechanism check

- Verdict: 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.
- Confidence: 8/10
- 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.

### Practical benchmark

- Paired seeds: 8
- Baseline mean: 0
- Idea mean: 0
- p-value: 0.5372
- Paired wins: 2/8
- Benchmark verdict: no significant win

## Artifacts

- [mom_experiment.py](https://synthcore.org/code/225/mom_experiment.py)
- [report.md](https://synthcore.org/code/225/report.md)
- [report_bench_2026-08-30T210710.md](https://synthcore.org/code/225/report_bench_2026-08-30T210710.md)
- [results/bench_report.json](https://synthcore.org/code/225/results/bench_report.json)
- [results/metrics.json](https://synthcore.org/code/225/results/metrics.json)
- [stage2_bench.py](https://synthcore.org/code/225/stage2_bench.py)
- [Download all files as ZIP](https://synthcore.org/download/225)

## Disclaimer

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