Faster algorithm and sharper analysis for constrained Markov decision process.

ABSTRACT: The problem of constrained Markov decision process (CMDP) is investigated, where an agent aims to maximize the expected accumulated reward subject to constraints on its utilities/costs. We propose a new primal-dual approach with a novel integration of entropy regularization and Nesterov's accelerated gradient method. The proposed approach is shown to converge to the global optimum with a complexity of 𝒪˜(1/ϵ) in terms of the optimality gap and the constraint violation, which improves the complexity of the existing primal-dual approaches by a factor of 𝒪(1/ϵ) .

SUBMITTER: Li T 

PROVIDER: S-EPMC12700660 | biostudies-literature | 2024 May

REPOSITORIES: biostudies-literature