We consider the problem of planning with participation constraints introduced
in [Zhang et al., 2022]. In this problem, a principal chooses actions in a
Markov decision process, resulting in separate utilities for the principal and
the agent. However, the agent can and will choose to end the process whenever
his expected onward utility becomes negative. The principal seeks to compute
and commit to a policy that maximizes her expected utility, under the
constraint that the agent should always want to continue participating. We
provide the first polynomial-time exact algorithm for this problem for
finite-horizon settings, where previously only an additive
$\varepsilon$-approximation algorithm was known. Our approach can also be
extended to the (discounted) infinite-horizon case, for which we give an
algorithm 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 additive
error of $\varepsilon$.

本文提出了针对参与限制问题的多项式时间精确算法，以计算并承诺最大化期望效用的策略，同时使代理人始终愿意参与，在有限和无限时间的情况下都可扩展应用。