Limits of Online Distributionally Robust Average-Reward Reinforcement Learning

We establish matching minimax horizon exponents for single-trajectory robust average-reward learning on tabular MDP families with bounded parameters. The learner observes transitions from an unknown nominal model $P$, while stationary policies are evaluated by their worst-case average reward over a rectangular $f$-divergence ball of radius $\delta$. The deletion cost ${\theta }_f$ measures the minimum divergence needed to remove a transition, while the asymptotic slope $f^{\prime }(\infty )$ determines whether new transitions can be created. These yield three exact radii ${\delta }_f^{\ast }(P)\le {\delta }_f^{†}(P)\le {\delta }_f^{bell}(P)$, characterizing, respectively, a common transition set guaranteeing weak communication, weak communication of every plausible model, and solvability of the robust Bellman equation with a state-independent gain for every bounded reward. For suitable fixed state and action counts and parameter bounds, minimax policy regret is $\tilde{\Theta }(\sqrt{T})$ when transition creation is impossible and $\delta <{\delta }^{bell}(P)$, even with nominal transient states. With creation and $0<\delta <{\theta }_f(1)$, the rate is $\tilde{\Theta }(T^{2/3})$ for communicating nominal MDPs, while linear regret can be unavoidable otherwise. At $\delta \ge {\theta }_f(1)$, every transition model is admissible and zero regret is achievable. A Bellman completion construction establishes the square-root upper bound beyond both communication thresholds.