Polynomial-Time Approximability of Constrained Reinforcement Learning

Jeremy McMahan

We study the computational complexity of approximating general constrained Markov decision processes. Our primary contribution is the design of a polynomial time $(0,\epsilon )$-additive b…