Anytime-Constrained Equilibria in Polynomial Time
원문 초록
We extend anytime constraints to the Markov game setting and the corresponding solution concept of an anytime-constrained equilibrium (ACE). Then, we present a comprehensive theory of anytime-constrained equilibria that includes (1) a computational characterization of feasible policies, (2) a fixed-parameter tractable algorithm for computing ACE, and (3) a polynomial-time algorithm for approximately computing ACE. Since computing a feasible policy is NP-hard even for two-player zero-sum games, our approximation guarantees are optimal so long as $P \neq NP$. We also develop the first theory of efficient computation for action-constrained Markov games, which may be of independent interest.
함께 살펴볼 논문
공통 태그를 근거로 연결했습니다. 실제 인용 관계나 논문의 우수성을 뜻하지 않습니다.
Biological Pathway Guided Gene Selection Through Collaborative Reinforcement Learning
Artificial Generals Intelligence: Mastering Generals.io with Reinforcement Learning
Multi-Agent Reinforcement Learning for Autonomous Multi-Satellite Earth Observation: A Realistic Case Study
Dynamic Reinsurance Treaty Bidding via Multi-Agent Reinforcement Learning
Wasserstein-Barycenter Consensus for Cooperative Multi-Agent Reinforcement Learning
Decentralizing Multi-Agent Reinforcement Learning with Temporal Causal Information
토론
이 논문과 연결된 포럼 글이 아직 없습니다.