Optimistic Policy Learning under Pessimistic Adversaries with Regret and Violation Guarantees

Real-world decision-making systems operate in environments where state transitions depend not only on the agent’s actions, but also on $\mathbf{\text{exogenous}}\mathbf{\text{factors}}\mathbf{\text{outside}}\mathbf{\text{its}}\mathbf{\text{control}}$–competing agents, environmental disturbances, or strategic adversaries–formally, $s_{h+1}=f(s_h,a_h,{\bar{a}}_h)+{\omega }_h$ where ${\bar{a}}_h$ is the adversary/external action, $a_h$ is the agent’s action, and ${\omega }_h$ is an additive noise. Ignoring such factors can yield policies that are optimal in isolation but $\mathbf{\text{fail}}\mathbf{\text{catastrophically}}\mathbf{\text{in}}\mathbf{\text{deployment}}$, particularly when safety constraints must be satisfied. Standard Constrained MDP formulations assume the agent is the sole driver of state evolution, an assumption that breaks down in safety-critical settings. Existing robust RL approaches address this via distributional robustness over transition kernels, but do not explicitly model the $\mathbf{\text{strategic}}\mathbf{\text{interaction}}$ between agent and exogenous factor, and rely on strong assumptions about divergence from a known nominal model. We model the exogenous factor as an $\mathbf{\text{adversarial}}\mathbf{\text{policy}}$ $\bar{\pi }$ that co-determines state transitions, and ask how an agent can remain both optimal and safe against such an adversary. \emph{To the best of our knowledge, this is the first work to study safety-constrained RL under explicit adversarial dynamics}. We propose $\mathbf{\text{Robust}}\mathbf{\text{Hallucinated}}\mathbf{\text{Constrained}}\mathbf{\text{Upper-Confidence}}\mathbf{\text{RL}}$ ($\mathtt{\text{RHC-UCRL}}$), a model-based algorithm that maintains optimism over both agent and adversary policies, explicitly separating epistemic from aleatoric uncertainty. $\mathtt{\text{RHC-UCRL}}$ achieves sub-linear regret and constraint violation guarantees.