Abstract
We consider the problem of planning with participation constraints introducedin [Zhang et al., 2022]. In this problem, a principal chooses actions in aMarkov decision process, resulting in separate utilities for the principal andthe agent. However, the agent can and will choose to end the process wheneverhis expected onward utility becomes negative. The principal seeks to computeand commit to a policy that maximizes her expected utility, under theconstraint that the agent should always want to continue participating. Weprovide the first polynomial-time exact algorithm for this problem forfinite-horizon settings, where previously only an additive$\varepsilon$-approximation algorithm was known. Our approach can also beextended to the (discounted) infinite-horizon case, for which we give analgorithm that runs in time polynomial in the size of the input and$\log(1/\varepsilon)$, and returns a policy that is optimal up to an additiveerror of $\varepsilon$.