Robust Q-learning drops the generative model: one Markovian trajectory suffices, with near-minimax sample complexity

Robust reinforcement learning can now be learned model-free from a single Markovian trajectory generated by a behavior policy, without estimating the transition kernel, at space cost on the order of storing the Q-function. Earlier model-free robust methods either required generative-model access to query arbitrary state-action pairs or, in the asynchronous setting, updated a dual variable by stochastic gradient ascent with a Q-function convergence rate markedly slower than standard Q-learning. Under a total-variation uncertainty set, the algorithm reaches an entrywise $\epsilon$ approximation with sample complexity of order $\frac{|S||A| t_{\mathrm{mix}}}{\epsilon^2 \mu_{\min}}$ up to logarithmic factors, where $t_{\mathrm{mix}}$ is the mixing time and $\mu_{\min}$ the minimum state-action occupancy probability of the trajectory's stationary distribution.

The algorithm replaces the worst-case expectation in the robust Bellman update with a single resampled surrogate next state, so the transition kernel need not be estimated explicitly. A total-variation uncertainty set permits at most $\rho$ probability mass to be shifted from high-value states to a minimum-value state, so the worst-case kernel is characterized by a threshold and a resampling probability. Thresholds and resampling probabilities are estimated online by bisection from trajectory samples, with the value function held fixed per stage to separate estimation from use; in numerical experiments on a two-state, two-action robust MDP, empirical sample complexity tracked the predicted dependence on effective horizon and uncertainty level.

The results cover discounted infinite-horizon, tabular, rectangular uncertainty sets defined by total-variation distance, with data from a single Markovian trajectory under one behavior policy; the authors also give the corresponding sample complexity for the generative-model (synchronous) setting.

The sample complexity carries an extra factor inherent to Q-learning relative to the minimax lower bound; the authors believe it is also unavoidable in the robust case but have not proven this, and the resampling scheme is tailored to total-variation uncertainty sets, with extension to other sets left for future work.