Learning Constrained Markov Decision Processes With Non-stationary Rewards and Constraints
<|reference_start|>Learning Constrained Markov Decision Processes With Non-stationary Rewards and Constraints: In constrained Markov decision processes (CMDPs) with adversarial rewards and constraints, a well-known impossibility result prevents any algorithm from attaining both sublinear regret and sublinear constraint violation, when competing against a best-in-hindsight policy that satisfies constraints on average. In this paper, we show that this negative result can be eased in CMDPs with non-stationary rewards and constraints, by providing algorithms whose performances smoothly degrade as non-stationarity increases. Specifically, we propose algorithms attaining $\tilde{\mathcal{O}} (\sqrt{T} + C)$ regret and positive constraint violation under bandit feedback, where $C$ is a corruption value measuring the environment non-stationarity. This can be $\Theta(T)$ in the worst case, coherently with the impossibility result for adversarial CMDPs. First, we design an algorithm with the desired guarantees when $C$ is known. Then, in the case $C$ is unknown, we show how to obtain the same results by embedding such an algorithm in a general meta-procedure. This is of independent interest, as it can be applied to any non-stationary constrained online learning setting.<|reference_end|>
@article{stradi2024learning,
    title={Learning Constrained Markov Decision Processes With Non-stationary
  Rewards and Constraints},
    author={Francesco Emanuele Stradi, Anna Lunghi, Matteo Castiglioni, Alberto
  Marchesi, Nicola Gatti},
    journal={arXiv preprint arXiv:2405.14372},
    year={2024},
    archivePrefix={arXiv},
    eprint={2405.14372},
    primaryClass={cs.LG}
}