Publication Type
Conference Proceeding Article
Version
publishedVersion
Publication Date
6-2023
Abstract
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.
Keywords
Action spaces, Action-constrained RL, Combinatorial action, Decision diagram, Knowledge compilation, Neuro-symbolic AI, Probabilistics, Reinforcement learnings, Resources allocation, Supply-demand
Discipline
Databases and Information Systems
Research Areas
Data Science and Engineering
Publication
Proceedings of the 22nd International Conference on Autonomous Agents and Multiagent Systems, London, Great Britain, 2023 May 29-June 2
First Page
860 - 86
Last Page
868
Publisher
International Foundation for Autonomous Agents and Multiagent Systems
City or Country
London
Citation
LING, Jiajing; SCHULER, Moritz Lukas; KUMAR, Akshat; and VARAKANTHAM, Pradeep.
Knowledge compilation for constrained combinatorial action spaces in reinforcement learning. (2023). Proceedings of the 22nd International Conference on Autonomous Agents and Multiagent Systems, London, Great Britain, 2023 May 29-June 2. 860 - 86-868.
Available at: https://ink.library.smu.edu.sg/sis_research/8592
Creative Commons License
This work is licensed under a Creative Commons Attribution-NonCommercial-No Derivative Works 4.0 International License.