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

CREATORDavid S. Hippocampus
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE538 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2502-04662

Browse the full library · About the Tower of Babel