  In robust Markov decision processes (RMDPs), it is assumed that the reward
and the transition dynamics lie in a given uncertainty set. By targeting
maximal return under the most adversarial model from that set, RMDPs address
performance sensitivity to misspecified environments. Yet, to preserve
computational tractability, the uncertainty set is traditionally independently
structured for each state. This so-called rectangularity condition is solely
motivated by computational concerns. As a result, it lacks a practical
incentive and may lead to overly conservative behavior. In this work, we study
coupled reward RMDPs where the transition kernel is fixed, but the reward
function lies within an $\alpha$-radius from a nominal one. We draw a direct
connection between this type of non-rectangular reward-RMDPs and applying
policy visitation frequency regularization. We introduce a policy-gradient
method and prove its convergence. Numerical experiments illustrate the learned
policy's robustness and its less conservative behavior when compared to
rectangular uncertainty.
