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 exogenous factors outside its control--competing agents, environmental disturbances, or strategic adversaries--formally, sh+1 = f(sh, ah, barah)+ωh where barah is the adversary/external action, ah is the agent's action, and ωh is an additive noise. Ignoring such factors can yield policies that are optimal in isolation but fail catastrophically in 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 strategic 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 adversarial policy barπ that co-determines state transitions, and ask how an agent can remain both optimal and safe against such an adversary. To the best of our knowledge, this is the first work to study safety-constrained RL under explicit adversarial dynamics. We propose Robust Hallucinated Constrained Upper-Confidence RL (textttRHC-UCRL), a model-based algorithm that maintains optimism over both agent and adversary policies, explicitly separating epistemic from aleatoric uncertainty. textttRHC-UCRL achieves sub-linear regret and constraint violation guarantees.