Optimal strategies for safe learning in adversarial decision processes
Toward Optimal Regret in Adversarial MDPs with Stochastic Hard Constraints
Machine Learning
Summary
This work focuses on making decisions in situations where outcomes can be unpredictable and constraints must be strictly followed at all times. The authors improve on earlier methods by proposing an algorithm that balances exploration and caution to safely learn the best strategy. Their approach ensures minimal mistakes over time while always respecting the cost limits. Importantly, they prove that their method is about as good as theoretically possible given the problem's challenges.
What this means in practice
- •For autonomous vehicle controllers: Develop decision-making algorithms that safely handle unpredictable environments while always satisfying safety constraints during operation.
- •For network resource managers: Optimize packet routing strategies in dynamic and potentially adversarial network conditions while ensuring quality-of-service constraints are met in real time.
Authors
Qian Zuo, Francesco Emanuele Stradi
Abstract
We study episodic constrained Markov decision processes with adversarial losses under stochastic hard constraints. Specifically, starting from a known strictly feasible policy with margin $d$, we seek to obtain optimal regret while satisfying the expected cost constraints in every episode. In this setting, Stradi et al. (2025) show that a carefully designed mixing rule attains regret of order $\widetilde{\mathcal{O}}(\sqrt{T}/\min\{d,d^2\})$. Interestingly, they also provide a lower bound of order $Ω(\sqrt{T}/ρ)$ for the same setting, where $ρ$ is the Slater margin of the offline problem and can be much larger than $d$. In this work, we build on their approach to obtain optimal regret dependence on these margins. Specifically, we propose MA-OPS, an algorithm that combines an optimistic search for the Slater margin with a pessimistic evaluation of the selected policies to safely learn a policy with a large feasibility margin. This policy is then used to minimize regret while satisfying the constraints at every episode. In particular, we show that MA-OPS attains regret $\widetilde{\mathcal{O}}(\sqrt{T}/ρ+ 1/(dρ))$. Finally, we provide a matching lower bound, showing that the dependence on $T$, $d$, $ρ$ in the regret bound is optimal up to logarithmic factors.