Adversarially-Robust TD Learning with Markovian Data

Policy evaluation is one of the most basic tasks in reinforcement learning: given a fixed policy, estimate the long-term return obtained by following it. Temporal Difference learning solves this problem without knowing the transition law or reward function. Its classical guarantees, however, assume that the observed rewards are reliably generated by the underlying Markov decision process. What happens if a small fraction of the rewards are replaced by arbitrary adversarial values?

The answer is surprisingly stark. Vanilla TD can converge to any point chosen by the adversary, even when the corruption probability is very small. The paper Adversarially-Robust TD Learning with Markovian Data: Finite-Time Rates and Fundamental Limits by Sreejeet Maity and Aritra Mitra develops a robust alternative and proves nearly matching upper and lower bounds. The difficult feature of the setting is that the clean data are not independent: they arrive along one Markov trajectory and may also be heavy-tailed.

Policy evaluation and the projected Bellman equation

Fix a policy $\mu$ in a discounted Markov decision process. The policy induces a Markov reward process with transition matrix $P_\mu$, mean reward vector $R_\mu$, and discount factor $\gamma\in(0,1)$. The value function satisfies the Bellman equation

\[V_\mu = R_\mu+\gamma P_\mu V_\mu.\]

When the state space is large, estimating one value per state may be infeasible. Linear function approximation instead uses feature vectors $\phi(s)\in\mathbb R^K$ and approximates

\[V_\mu(s) \approx \widehat V_\theta(s) = \phi(s)^\top\theta.\]

Let $\Phi$ be the feature matrix and let $D$ be the diagonal matrix containing the stationary distribution $\pi$ of the Markov chain induced by $\mu$. The target parameter $\theta^\star$ is the unique solution of the projected Bellman equation

\[\Pi_D\mathcal T_\mu(\Phi\theta^\star) = \Phi\theta^\star,\]

where $\Pi_D$ projects onto the feature subspace in the $D$-weighted norm. Equivalently,

\[\overline A\theta^\star+\overline b=0,\]

with

\[\overline A = \Phi^\top D(\gamma P_\mu-I)\Phi, \qquad \overline b = \Phi^\top D R_\mu.\]

This linear system is the deterministic object that TD attempts to solve using samples.

TD as stochastic approximation

At time $t$, the learner observes a transition $s_t\to s_{t+1}$ and a reward $r_t$. The TD direction can be written in affine form as

\[g_t(\theta) = A_t\theta+b_t,\]

where

\[A_t = \gamma\phi(s_t)\phi(s_{t+1})^\top - \phi(s_t)\phi(s_t)^\top, \qquad b_t = \phi(s_t)r_t.\]

The ordinary TD update is

\[\theta_{t+1} = \theta_t+\alpha_t(A_t\theta_t+b_t).\]

At stationarity, $\mathbb E[A_t]=\overline A$ and $\mathbb E[b_t]=\overline b$. Thus the mean update points toward the solution of $\overline A\theta+\overline b=0$. The analysis is already subtler than an i.i.d. stochastic-gradient argument because $A_t$, $b_t$, and $\theta_t$ are coupled through a single Markov trajectory.

Huber-contaminated rewards

The clean reward at state $s$ is drawn from a distribution with mean $R_\mu(s)$ and variance at most $\rho^2$. No sub-Gaussian tail is assumed. The observed reward is

\[\widetilde r_t \sim (1-\varepsilon)\mathcal D_\mu(\cdot\mid s_t) + \varepsilon\mathcal Q_t,\]

where $\mathcal Q_t$ is arbitrary and may be chosen by an adversary. Equivalently, with probability $1-\varepsilon$ the reward is clean, while with probability $\varepsilon$ it is replaced by an unconstrained value.

Two uncertainties now interact. The learner must distinguish clean heavy-tailed observations from outliers, and it must do so using temporally dependent data. Classical robust mean estimators typically assume independent inliers, whereas standard TD analyses assume uncorrupted rewards. Neither theory can be inserted unchanged.

The vulnerability of vanilla TD

The paper first isolates the effect of corruption by considering deterministic corrupted rewards. Let \(C\in\mathbb R^{|\mathcal S|}\) collect the adversarial reward values. Under the usual Robbins-Monro step-size conditions, vanilla TD converges almost surely to

\[\widetilde\theta^\star = (1-\varepsilon)\theta^\star + \varepsilon \left(-\overline A^{-1}\Phi^\top D C\right).\]

This formula makes the failure mechanism transparent. The first term is the desired solution. The second is an adversarial direction transmitted through the inverse of the TD system matrix. Because the attacker controls $C$, it can choose this second term so that $\widetilde\theta^\star$ equals any prescribed vector in $\mathbb R^K$.

Small corruption probability is therefore not enough. The quantity $\varepsilon C$ can be arbitrarily large because the model places no bound on the attack magnitude. As with corrupted $Q$-Learning, ordinary convergence proves only that the stochastic approximation has settled at a fixed point; it does not certify that the fixed point is the correct one.

Robust mean estimation with Markovian data

The key statistical subroutine is RUMEM, a Robust Univariate Mean Estimator for Markovian data. To understand it, suppose $X_1,X_2,\ldots$ is an ergodic stationary Markov chain and a clean scalar observation $f(X_t)$ has stationary mean $\overline f$ and finite variance. The observed samples are Huber contaminated.

RUMEM uses three operations. First, it subsamples the trajectory, retaining one observation every $\tau$ time steps. If $\tau$ is chosen using the mixing time, the retained observations are close to independent. Second, it divides the retained samples into buckets and computes the mean within each bucket. Third, it outputs the median of these bucket means.

Let $N$ be the original number of observations. The theorem for RUMEM gives, with high probability,

\[|\widehat\mu-\overline f| \leq C\max\{\psi,\rho\} \left( \sqrt\varepsilon + \sqrt{ \frac{\tau}{N} \log\left(\frac{N}{\delta}\right) } \right),\]

where \(|\mathbb E[f(X_t)\mid X_t=x]|\leq\psi\) and $\rho^2$ bounds the conditional variance. The factor $\tau$ expresses the effective-sample-size penalty: $N$ correlated samples behave roughly like $N/\tau$ independent samples.

This result is more than a technical lemma for TD. It shows that a median-of-means construction can simultaneously tolerate heavy tails, adversarial contamination, and Markovian dependence.

Building Robust-TD

Only the affine term $b_t=\phi(s_t)\widetilde r_t$ contains the corrupted reward. This suggests estimating the stationary vector

\[\overline b = \mathbb E_{s\sim\pi,r\sim\mathcal D_\mu(\cdot\mid s)} [\phi(s)r]\]

robustly, while leaving the transition-dependent matrix $A_t$ unchanged.

For each coordinate $i\in[K]$, Robust-TD forms the historical scalar sequence

\[y_{i,k} = [\phi(s_k)]_i\widetilde r_k\]

and applies RUMEM to estimate $[\overline b]_i$. Stacking the coordinatewise estimates produces $\widehat b_t$.

This estimate is accurate with high probability, but it can still be extreme on a rare event. Robust-TD therefore introduces a dynamic threshold. If

\[\|\widehat b_t\|_2>G_t+\sigma_1,\]

the estimate is reset to zero. Here $\sigma_1=\max{1,\overline r,\rho}$, and the threshold has the form

\[G_t \asymp \sqrt K\,\sigma_1 \left( \sqrt\varepsilon + \sqrt{ \frac{\tau_{\mathrm{mix}}\log(KT)}{t} } \right).\]

The robust update direction is

\[\widetilde g_t(\theta_t) = A_t\theta_t+\widehat b_t,\]

and the parameter update is

\[\theta_{t+1} = \theta_t+\alpha\widetilde g_t(\theta_t).\]

The algorithm waits through a logarithmic burn-in period before updating. This ensures that enough data have accumulated for the robust estimates to be informative.

The finite-time upper bound

Let

\[\Sigma=\Phi^\top D\Phi, \qquad \omega=\lambda_{\min}(\Sigma)>0.\]

The parameter $\omega$ measures feature coverage. If $\omega$ is small, some feature direction receives very little information under the stationary distribution. Define

\[\mathcal G = \frac{K}{\omega^2(1-\gamma)^2},\]

and let $\overline\tau_{\mathrm{mix}}$ denote the relevant maximum of the chain’s mixing scales. For a suitable constant step size of order $\log(T)/(\omega(1-\gamma)T)$, the paper proves

\[\mathbb E\left[\|\theta_T-\theta^\star\|_2^2\right] \leq \widetilde O\left( \frac{\overline\tau_{\mathrm{mix}}\sigma^2\mathcal G}{T} \right) + O\left( \varepsilon\sigma_1^2\mathcal G \right),\]

where $\sigma$ controls the sizes of the target, initialization, and reward scale.

The first term is the ordinary finite-time TD error under Markovian sampling. When $\varepsilon=0$, it agrees with established TD rates up to logarithmic factors. The second is the corruption floor in mean-square error. Consequently, the corresponding root-mean-square parameter error scales as $\sqrt\varepsilon$.

The dependence on $1/\omega^2$ is intuitive. In the tabular case, $\omega$ reduces to the smallest stationary state probability. An infrequently visited state gives the learner few clean samples, making robust estimation harder and allowing corruption to have a larger effect.

The minimax lower bound

The paper complements the algorithmic guarantee with an information-theoretic lower bound. Even in a simpler i.i.d. tabular observation model, there is a universal constant $c>0$ such that

\[\inf_{\widehat V_T} \sup_{V\in\mathfrak M(\varepsilon,\rho,\mathcal Q)} \mathbb P\left( \|\widehat V_T-V\|_2 \geq \frac{c\rho\sqrt\varepsilon}{1-\gamma} \right) \geq \frac12.\]

The proof constructs two different Markov reward processes whose true value functions are separated by order $\rho\sqrt\varepsilon/(1-\gamma)$, but whose contaminated observation distributions are indistinguishable. If the learner cannot statistically tell which process generated the data, it cannot be accurate on both.

This result shows that the $\sqrt\varepsilon$ value-estimation error, the reward-noise scale $\rho$, and the effective-horizon factor $1/(1-\gamma)$ are all fundamental. The upper bound has an $O(\varepsilon)$ term because it controls squared parameter error; after taking a square root, it agrees with the lower-bound scaling.

The central proof difficulty

Two biases appear in the Robust-TD recursion. The first is the Markovian bias

\[\langle \theta_t-\theta^\star, (A_t-\overline A)\theta_t \rangle.\]

The second is the robust-estimation error

\[\langle \theta_t-\theta^\star, \widehat b_t-\overline b \rangle.\]

These terms cannot be analyzed independently because the adversarial error affects $\theta_t$, and $\theta_t$ appears inside the Markovian bias. The proof first establishes a quantitative bound on $\mathbb E|\widehat b_t-\overline b|_2^2$ using RUMEM and thresholding. It then controls the drift of the stochastic approximation while using mixing to compare time-dependent conditional expectations with their stationary counterparts.

This coupling is what makes the result substantially harder than either robust mean estimation or ordinary TD analysis alone. Robust statistics supplies an estimate of $\overline b$; mixing theory controls the temporal dependence; and the negative drift induced by the projected Bellman equation keeps the parameter recursion stable.

What the result says and does not say

Robust-TD prevents the attack magnitude from appearing in the final guarantee. Arbitrarily large outliers are reduced to an error determined by the corruption probability and the intrinsic reward variance. The algorithm also avoids a projection step on the TD iterates, which is significant because projection would require prior knowledge of a suitable parameter radius.

The result assumes linear function approximation, reward-only corruption, a stationary initialization for the main theorem, knowledge of the corruption level, and access to mixing information for tuning the subsampling gap. It does not yet treat corrupted transitions or nonlinear function approximation. Even with these limitations, the paper establishes a clean conceptual benchmark: under Markovian sampling and finite-variance rewards, robust policy evaluation is possible at the ordinary statistical rate plus the smallest corruption penalty one can generally expect.