Knowledge compilation for constrained combinatorial action spaces in reinforcement learning

• Main Authors: LING, Jiajing, SCHULER, Moritz Lukas, KUMAR, Akshat, VARAKANTHAM, Pradeep
• Format: text
• Language: English
• Published: Institutional Knowledge at Singapore Management University 2023
• Subjects: Action spaces; Action-constrained RL; Combinatorial action; Decision diagram; Knowledge compilation; Neuro-symbolic AI; Probabilistics; Reinforcement learnings; Resources allocation; Supply-demand; Databases and Information Systems
• Online Access: https://ink.library.smu.edu.sg/sis_research/8592; https://ink.library.smu.edu.sg/context/sis_research/article/9595/viewcontent/Knowledge_Compilation_for_Constrained_Combinatorial_Action_Spaces_in_Reinforcement_Learning.pdf
• Institution: Singapore Management University

Action-constrained reinforcement learning (ACRL), where any action taken in a state must satisfy given constraints, has several practical applications such as resource allocation in supply-demand matching, and path planning among others. A key challenge is to enforce constraints when the action space is discrete and combinatorial. To address this, first, we assume an action is represented using propositional variables, and action constraints are represented using Boolean functions. Second, we compactly encode the set of all valid actions that satisfy action constraints using a probabilistic sentential decision diagram (PSDD), a recently proposed knowledge compilation framework. Parameters of the PSDD compactly encode the probability distribution over all valid actions. Consequently, the learning task becomes optimizing PSDD parameters to maximize the RL objective. Third, we show how to embed the PSDD parameters using deep neural networks, and optimize them using a deep Q-learning based algorithm. By design, our approach is guaranteed to never violate any constraint, and does not involve any expensive projection step over the constraint space. Finally, we show how practical resource allocation constraints can be encoded using a PSDD. Empirically, our approach works better than previous ACRL methods, which often violate constraints, and are not scalable as they involve computationally expensive projection-over-constraints step.