Adversarially-Robust TD Learning with Markovian Data: Finite-Time Rates and Fundamental Limits
David S. Hippocampus · 2025
Read Adversarially-Robust TD Learning with Markovian Data: Finite-Time Rates and Fundamental Limits by David S. Hippocampus (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2502-04662.txt.
Description
Temporal difference learning is the workhorse for judging a policy in reinforcement learning: it estimates long-run returns from a stream of rewards. Sreejeet Maity and Aritra Mitra ask in 2025 what happens when an adversary can corrupt a small share of those rewards, as harsh real environments might. Under such Huber-style contamination, they first show the standard algorithm can be pushed to converge to any value function at all — a total breakdown.
Their answer is Robust-TD, a hardened variant. Its finite-time guarantees match the clean algorithm's, up to a small extra term proportional to the corruption rate. A matching lower bound proves that extra term cannot be avoided by any method. The key tool is a median-of-means estimator adapted to corrupted, time-correlated data, which the authors note may serve robust statistics more broadly.
Catalog record
| CREATOR | David S. Hippocampus |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 538 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2502-04662