Efficient algorithm learns constrained decision processes with optimal regret rate
Learning Infinite-Horizon Average-Reward CMDPs via State Augmentation
Machine Learning
Summary
This paper tackles a problem called constrained Markov decision processes, where decisions have to balance rewards and limitations over an infinite time horizon. The authors developed a new efficient method that learns to make decisions with the lowest possible mistake rate while respecting constraints. They do this by cleverly expanding the state to include past constraint violations and reshaping rewards, which helps in applying known techniques from simpler decision problems. Their solution improves on previous work by being both practical to run and mathematically optimal in terms of learning speed.
What this means in practice
- •For robotics engineers: Optimize robot control policies that must satisfy safety constraints over long missions without sacrificing learning efficiency.
- •For network traffic managers: Develop resource allocation strategies that balance performance with constraints like bandwidth limits using more sample-efficient learning algorithms.
Authors
Kihyun Yu, Seoungbin Bae, Dabeen Lee
Abstract
We study infinite-horizon average-reward constrained Markov decision processes (CMDPs) under the weakly communicating assumption. Existing high-probability guarantees for this setting either require computationally inefficient algorithms or have suboptimal dependence on the number of interactions $T$. We propose, to the best of our knowledge, the first computationally efficient algorithm that achieves $\widetilde{\mathcal{O}}(\sqrt{T})$ regret and cumulative constraint violation with high probability in the tabular setting. The $\sqrt{T}$ dependence is optimal up to logarithmic factors. Our approach incorporates cumulative constraint violation into the state and defines a reshaped reward through differences of a Huber potential. The added state determines the penalty on further violations while the reward function remains fixed on the augmented state space. Since the added state has known deterministic dynamics, only the original transition kernel needs to be estimated. The bounded slope of the Huber potential keeps the per-step reward bounded, and the potential differences telescope to relate the reshaped return to the original cumulative reward and the terminal potential. These properties allow us to apply finite-horizon approximation and optimistic value iteration with clipping, as used in unconstrained average-reward MDPs, without worsening the regret rate in $T$.