Efficient Algorithms for Planning with Participation Constraints
Efficient Algorithms for Planning with Participation Constraints
复制标题
具有参与约束的规划的高效算法
DOI：
10.1145/3490486.3538280
复制
发表时间：
2022
期刊：
影响因子：
--
通讯作者：
Conitzer, Vincent
中科院分区：
文献类型：
--
作者：
Zhang, Hanrui;Cheng, Yu;Conitzer, Vincent
我们考虑了[24]中引入的具有参与限制的规划问题。在这个问题中，委托人在马尔可夫决策过程中选择行为，导致委托人和代理人的效用分离。然而，代理可以并且将选择在其预期的向前效用变为负数时结束该过程。委托人寻求计算并承诺一个策略，在代理人应该始终想要继续参与的约束下，最大化她的预期效用。我们给出了这一问题的第一个多项式时间精确算法，在此之前，我们只知道一个加性的ε-近似算法。我们的方法也可以推广到(折扣)无限水平的情况，对于这种情况，我们给出了一个算法，它以输入和LOG(1/ε)的大小在时间多项式中运行，并且返回一个直到ε的可加误差的最优策略。
We consider the problem of planning with participation constraints introduced in[24]. 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 ε-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/ε), and returns a policy that is optimal up to an additive error of ε.
登录
查看更多内容
动态评估设计
DOI：
--
发表时间：
2017
期刊：
American Economic Journal: Microeconomics
影响因子：
--
作者：
Alex Smolin
通讯作者：
Alex Smolin
重新审视多链马尔可夫决策过程中的线性规划方法
DOI：
10.1007/bf01415752
发表时间：
1995
期刊：
Zeitschrift für Operations Research
影响因子：
--
作者：
E. Altman;F. Spieksma
通讯作者：
F. Spieksma
动态机制设计：鲁棒性和内生类型
影响因子：
2.2
作者：
A. Pavan
通讯作者：
A. Pavan
去中心化 POMDP
影响因子：
5.7
作者：
F. Oliehoek
通讯作者：
F. Oliehoek
具有参与约束的规划
DOI：
10.1609/aaai.v36i5.20462
发表时间：
2022
期刊：
Proceedings of the 36th AAAI Conference on Artificial Intelligence
影响因子：
--
作者：
Zhang, Hanrui;Cheng, Yu;Conitzer, Vincent
通讯作者：
Conitzer, Vincent