Efficient Algorithms for Planning with Participation Constraints
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$.